- 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