- 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 corner points , where and are real numbers between and . These points form a polygon with corners and sides. You know that 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 squares, labelled with pairs that range from to . For each square , Paola colors it black if point is inside polygon , and otherwise it is white. This is the bitmap image that you will get.
Input
The first input line has one integer : 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
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