Scrambled Digits

Little Petya started to learn how to write some digits. He is just learning to write the following 5 digits:

He draws each digit with exactly the same dimensions as the image above, but he may apply zero or more of the following updates:

• Shrink or expand the width of the digit, keeping the width an integer number of units.
• Shrink or expand the height of the digit, keeping the height an integer number of units.
• Rotate the digit clockwise by 90, 180, or 270 degrees.

Shrinking or expanding a digit does not change the thickness of its segments, and it affects the whole digit equally. For example, shrinking or expanding the digit 3 vertically (before rotating it) always keeps the middle horizontal segment exactly in the middle between the other horizontal segments.

Petya writes many digits on an infinite 2D plane and keeps these rules valid:

• Digits do not touch or overlap each other. The segments of one digit do not touch the segments of another digit.
• All vertical segments lie on a vertical line with an integer X-value.
• All horizontal segments lie on a horizontal line with an integer Y-value.
• All end points have integer coordinates. An end point is a point at the end of a vertical or horizontal segment.

Petya draws digits with line segments. Each segment starts and ends at integer coordinates, and each segment is vertical or horizontal with a positive integer length. Segments may touch or even overlap, but when they do, they belong to the same instance of the same digit (see the second sample test case).

The following image shows some invalid digits that never appear in the input:

The 1 is rotated incorrectly, the middle horizontal segment of the 3 has the wrong length, the middle horizontal segment of the 2 is no longer in the middle, and the 4 is mirrored instead of rotated.

You are given a list of line segments that Petya drew. The input is guaranteed to form only valid digits as described above. Count how many times each digit was drawn.

The first line contains a single integer T, the number of test cases (1 ≤ T ≤ 100). Each test case starts with a line containing an integer N, the number of segments (1 ≤ N ≤ 100,000). Then N lines follow, each containing four integers $X_1$, $Y_1$, $X_2$, and $Y_2$, which describe a segment between the points $(X_1, Y_1)$ and $(X_2, Y_2)$, where 1 ≤ X1, Y1, X2, Y2 ≤ 1,000,000,000.

For each test case, print 5 integers separated by a single space. Each integer is the number of times the corresponding digit was drawn, in the same left-to-right order as the first image.

The first sample test case shows the first image.

The second sample test case shows the following image. Some segments overlap or touch to form one longer segment.