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 input file is numbers.in.

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 file is numbers.out.

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

(See sample.in in the problem directory)

Output 1

(See sample.out in the problem directory)

Image Files

For the sample and the first 10,000 images of the test data, BMP format images are provided, named sample.bmp and 10000.bmp respectively. Among them, 10000.bmp has 100 digits per row, for a total of 100 rows.

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

Subtasks

If the number of digits you output is less than $n$, we will compare them with the first $n$ digits. If the count exceeds $n$ or the format is incorrect, 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.

How to Test Your Output

You can use the checker to test whether your output meets the format requirements. To use it, first open a terminal and run the following command to enter the directory of this problem:

cd numbers

Then run the following command:

./checker numbers.out

If your output is valid, you will see how many integers the checker successfully read.

If the output is invalid, you will see the reason for the error, which may include: list.txt not found, $n$ is out of range, or grayscale values are out of range.

If you wish to test other output filenames, you can replace numbers.out with your desired filename.

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.

File List

There are relatively many files for this problem. The purpose of each file is summarized below:

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