In the past, Mr. B did not have a mobile phone. He used a phone book to store all his numbers. Now that Mr. B has a phone, he wants to store all the numbers in it, but he finds that entering the numbers one by one is very inefficient. So, he turned to his good friend Mr. R for help.

Mr. R suggested that if the numbers are scanned into images, and each digit is processed as a $28 \times 28$ grayscale image, it would be easier to recognize them. The previous work is a piece of cake for Mr. B, but the final step of recognition leaves Mr. B at a loss, so he asks you to identify what these digits are.

Mr. B does not mind you seeing his friends' phone numbers, so this is an answer-submission problem.

Input

The first line of the input contains one integer $n$, representing the number of images. The number of rows and columns for each image is fixed at 28.

Following this are $n$ parts, each part being a $28 \times 28$ matrix. Each entry in the matrix is an integer between 0 and 255, representing the grayscale value at that position. Here, 0 represents white and 255 represents black. (This is the opposite of typical grayscale images.)

Output

The output contains $n$ lines, each containing one digit, representing what you believe that digit is (the result of the digit recognition).

Examples

Input 1

(input data)

Output 1

(output data)

Note

Mr. B notes that handwritten digits can have many variations. For example, 1 can have a serif, 7 might have a horizontal bar added, and 4 might not have an extended stroke on the right or might be closed at the top. You can see similar writing styles in the sample and the first 10,000 data points.

Subtasks

If the number of digits you output is less than $n$, we will compare them with the first $n$ digits. If the number of errors exceeds the limit, you will receive 0 points.

Because different data have different importance, the point value for each part is different: First 1000 data points: 1/100 points each. Next 2000 data points: 1/200 points each. Next 3000 data points: 1/300 points each. Next 4000 data points: 1/400 points each. Next 5000 data points: 1/500 points each. Next 7000 data points: 1/700 points each. Next 8000 data points: 1/800 points each. Next 9000 data points: 1/900 points each. Next 10000 data points: 1/1000 points each. Next 11000 data points: 1/1100 points each.

A total of 60,000 data points, with a total of 100 points. Since the final score must be an integer, the score will be rounded.

Mr. B is very lenient and does not mind if you make recognition errors, so errors will not incur additional penalties.

Implementation Details

For the sample and the first 10,000 images of the test data, images are provided. The 10,000-image file has 100 digits per row, for a total of 100 rows.

In addition, there is a provided program. You can create a text file in the same directory as this program, and then run this program to generate an image file. It can convert up to 100 images at a time. The format of the text file is the same as the input format. In other words, you can copy the input data to a text file to generate an image with the same format as the sample image.

Please pay attention to saving and backing up in time to prevent accidental operations.