Euclidean Geometry

• Time limit: 1.00 s
• Memory limit: 512 MB

Paola draws a polygon and sends you a bitmap image of it. Your task is simple: find out whether the polygon has 3 or 4 corners!

You know that Paola has picked $k$ corner points $(x_1, y_1), \dotsc, (x_k, y_k)$, where $x_i$ and $y_i$ are real numbers between $1$ and $100$. These $k$ points form a polygon $P$ with $k$ corners and $k$ sides. You know that $k$ is 3 or 4, so we have a triangle or a quadrilateral. The polygon is simple, i.e., it does not intersect itself. Paola also promised that each side is at least 20 units long, and each angle is at least 30° and at most 120°.

Paola then takes a grid paper with $100 \times 100$ squares, labelled with $(x,y)$ pairs that range from $(1,1)$ to $(100,100)$. For each square $(x,y)$, Paola colors it black if point $(x,y)$ is inside polygon $P$, and otherwise it is white. This is the bitmap image that you will get.

Input

The first input line has one integer $t$: the number of images.

Each image consists of 100 lines. Each line contains 100 characters; each character is either "0" or "1". These lines represent Paola's bitmap image: 0 is white (outside polygon) and 1 is black (inside polygon).

Output

For each image, print one number: the number of corners in the polygon. The answer is always either 3 or 4.

Constraints

• $1 \le t \le 100$
  

Example

Input:
1
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000011000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000001111100000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000011111100000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000001111111100000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000011111111110000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000001111111111110000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000011111111111110000000000000000000000000
0000000000000000000000000000000000000000000000000000000000001111111111111111000000000000000000000000
0000000000000000000000000000000000000000000000000000000000011111111111111111000000000000000000000000
0000000000000000000000000000000000000000000000000000000001111111111111111111100000000000000000000000
0000000000000000000000000000000000000000000000000000000011111111111111111111100000000000000000000000
0000000000000000000000000000000000000000000000000000000111111111111111111111100000000000000000000000
0000000000000000000000000000000000000000000000000000011111111111111111111111110000000000000000000000
0000000000000000000000000000000000000000000000000000111111111111111111111111110000000000000000000000
0000000000000000000000000000000000000000000000000011111111111111111111111111110000000000000000000000
0000000000000000000000000000000000000000000000000111111111111111111111111111111000000000000000000000
0000000000000000000000000000000000000000000000011111111111111111111111111111111000000000000000000000
0000000000000000000000000000000000000000000000111111111111111111111111111111111100000000000000000000
0000000000000000000000000000000000000000000011111111111111111111111111111111111100000000000000000000
0000000000000000000000000000000000000000000111111111111111111111111111111111111100000000000000000000
0000000000000000000000000000000000000000001111111111111111111111111111111111111110000000000000000000
0000000000000000000000000000000000000000111111111111111111111111111111111111111110000000000000000000
0000000000000000000000000000000000000001111111111111111111111111111111111111111110000000000000000000
0000000000000000000000000000000000000111111111111111111111111111111111111111111111000000000000000000
0000000000000000000000000000000000001111111111111111111111111111111111111111111111000000000000000000
0000000000000000000000000000000000111111111111111111111111111111111111111111111111000000000000000000
0000000000000000000000000000000001111111111111111111111111111111111111111111111111100000000000000000
0000000000000000000000000000000111111111111111111111111111111111111111111111111111100000000000000000
0000000000000000000000000000001111111111111111111111111111111111111111111111111111110000000000000000
0000000000000000000000000000111111111111111111111111111111111111111111111111111111110000000000000000
0000000000000000000000000001111111111111111111111111111111111111111111111111111111110000000000000000
0000000000000000000000000011111111111111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000001111111111111111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000011111111111111111111111111111111111111111111111111111111111111000000000000000
0000000000000000000001111111111111111111111111111111111111111111111111111111111111111100000000000000
0000000000000000000011111111111111111111111111111111111111111111111111111111111111111100000000000000
0000000000000000001111111111111111111111111111111111111111111111111111111111111111111110000000000000
0000000000000000011111111111111111111111111111111111111111111111111111111111111111111110000000000000
0000000000000001111111111111111111111111111111111111111111111111111111111111111111111110000000000000
0000000000000011111111111111111111111111111111111111111111111111111111111111111111111111000000000000
0000000000000111111111111111111111111111111111111111111111111111111111111111111111111111000000000000
0000000000011111111111111111111111111111111111111111111111111111111111111111111111111111000000000000
0000000000111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000
0000000011111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000
0000000001111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000
0000000000011111111111111111111111111111111111111111111111111111111111111111111111111111110000000000
0000000000000111111111111111111111111111111111111111111111111111111111111111111111111111110000000000
0000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111000000000
0000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111000000000
0000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111000000000
0000000000000000000001111111111111111111111111111111111111111111111111111111111111111111110000000000
0000000000000000000000011111111111111111111111111111111111111111111111111111111111111111100000000000
0000000000000000000000000111111111111111111111111111111111111111111111111111111111111111000000000000
0000000000000000000000000001111111111111111111111111111111111111111111111111111111111100000000000000
0000000000000000000000000000011111111111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000000000000111111111111111111111111111111111111111111111111111110000000000000000
0000000000000000000000000000000001111111111111111111111111111111111111111111111111100000000000000000
0000000000000000000000000000000000011111111111111111111111111111111111111111111111000000000000000000
0000000000000000000000000000000000001111111111111111111111111111111111111111111110000000000000000000
0000000000000000000000000000000000000011111111111111111111111111111111111111111100000000000000000000
0000000000000000000000000000000000000000111111111111111111111111111111111111111000000000000000000000
0000000000000000000000000000000000000000001111111111111111111111111111111111110000000000000000000000
0000000000000000000000000000000000000000000011111111111111111111111111111111100000000000000000000000
0000000000000000000000000000000000000000000000111111111111111111111111111111000000000000000000000000
0000000000000000000000000000000000000000000000001111111111111111111111111110000000000000000000000000
0000000000000000000000000000000000000000000000000011111111111111111111111000000000000000000000000000
0000000000000000000000000000000000000000000000000000111111111111111111110000000000000000000000000000
0000000000000000000000000000000000000000000000000000001111111111111111100000000000000000000000000000
0000000000000000000000000000000000000000000000000000000011111111111111000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000111111111110000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000001111111100000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Output:
4