You have an Art History exam approaching, but you have been paying more attention to informatics at school than to your art classes! You will need to write a program to take the exam for you.

The exam will consist of several paintings. Each painting is an example of one of four distinctive styles, numbered ~1~, ~2~, ~3~ and ~4~.

Style ~1~ contains neoplastic modern art. For example:

Style ~2~ contains impressionist landscapes. For example:

Style ~3~ contains expressionist action paintings. For example:

Style ~4~ contains color field paintings. For example:

Your task is, given a digital image of a painting, to determine which style the painting belongs to.

The IOI judges have collected many images in each style. Nine images from each style have been chosen at random and included in the task materials on your computer, so that you can examine them by hand and use them for testing. The remaining images will be given to your program during grading.

The image will be given as an ~H \times W~ grid of pixels. The rows of the image are numbered ~0, \dots, H-1~ from top to bottom, and the columns are numbered ~0, \dots, W-1~ from left to right.

The pixels are described using two-dimensional arrays ~R~, ~G~ and ~B~, which give the amount of red, green and blue respectively in each pixel of the image. These amounts range from ~0~ (no red, green or blue) to ~255~ (the maximum amount of red, green or blue).

Input Specification

The first line of input will contain the integer ~T~ ~(0 \le T \le 150)~, the number of test cases to follow.

For each test case:

• The first line will contain the two integers ~H~ and ~W~, the height and width of the image.
• The next ~H~ lines will each contain ~W~ integers. Each integer will describe a pixel using the default RGB color model (see below for conversion instructions).

Output Specification

For every test case, output a line containing a single integer denoting the style of the image, which must be ~1~, ~2~, ~3~ or ~4~, as described above.

Sample Tests

Individual sample test cases for the above images can be found here for you to analyse (Right click > Save link as):

• Style ~1~ - style-1-0.in, style-1-1.in, style-1-2.in, style-1-3.in
• Style ~2~ - style-2-0.in, style-2-1.in, style-2-2.in, style-2-3.in
• Style ~3~ - style-3-0.in, style-3-1.in, style-3-2.in, style-3-3.in
• Style ~4~ - style-4-0.in, style-4-1.in, style-4-2.in, style-4-3.in

Interpreting Colors

The standard conversion scheme with RGB colors uses the formula: RGB = (R<<16)|(G<<8)|B, where ~R, G~ and ~B~ are values from ~0~ to ~255~ inclusive, << is the bitshift-left operator, and | is the bitwise-OR operator. To obtain the RGB values from an individual encoded integer pixel, use the following functions:

C/C++

int getR(int RGB) { return (RGB >> 16) & 0xFF; }

int getG(int RGB) { return (RGB >> 8) & 0xFF; }

int getB(int RGB) { return RGB & 0xFF; }

Pascal

function getR(RGB: longint): integer;
begin getR := (RGB shr 16) and $FF; end;

function getG(RGB: longint): integer;
begin getG := (RGB shr 8) and $FF; end;

function getB(RGB: longint): integer;
begin getB := RGB and $FF; end;

Constraints

~100 \le H \le 500~

~100 \le W \le 500~

Scoring

There are no subtasks. Instead, your score for this task will be based on how many images your program correctly classifies.

Suppose you correctly classify ~P~ percent of the images (so ~0 \le P \le 100~):

• If ~P < 25~ then you will score ~0~ points.
• If ~25 \le P < 50~ then you will score between ~0~ and ~10~ points, on a linear scale.
  Specifically, your score will be ~10 \times (P-25) / 25~, rounded down to the nearest integer.
• If ~50 \le P < 90~ then you will score between ~10~ and ~100~ points, on a linear scale.
  Specifically, your score will be ~10 + (90 \times (P-50) / 40)~, rounded down to the nearest integer.
• If ~90 \le P~ then you will score ~100~ points.