Time Limit:1000ms Memory Limit:65536KB

Description

Mengqian has attracted overwhelming boys after March 11. Mengqian claims that she
preferred the boy with persistence. In order to choose her boy, she delegated the
ACM team of UESTC to publish her puzzle.
The puzzle is called ¡°Persistence of Number¡±, which consists of 32 nonnegative
integers, each 32-digit long. Then she asked suitors to calculate the persistence
of the product of the 32 integers. The one who first solve this puzzle would win
Mengqian¡¯s heart.
The persistence of an integer denotes a digit generated by replace the integer by
the sum of its digits until one reaches a single digit. For example, the
persistence of 19890902 is 2, because 1 + 9 + 8 + 9 + 0 + 9 + 0 + 2 = 38, 3 + 8 =
11, 1 + 1 = 2.
Wolverine is a crazy suitor of Mengqian with brilliant minds. He said he can
solve this problem in ten minutes. Can you beat him?

Input

The first line of the input is an integer T (T <= 311), which stands for the
number of test cases you need to solve. Each case consist of 32 lines, each line
denotes a 32-digit long integer.

Output

For each case, print a digit on a single line, which is the persistence of the
product of the 32 integers.

Sample Input

1
10000000000000000000000000000000
01000000000000000000000000000000
00100000000000000000000000000000
00010000000000000000000000000000
00001000000000000000000000000000
00000100000000000000000000000000
00000010000000000000000000000000
00000001000000000000000000000000
00000000100000000000000000000000
00000000010000000000000000000000
00000000001000000000000000000000
00000000000100000000000000000000
00000000000010000000000000000000
00000000000001000000000000000000
00000000000000100000000000000000
00000000000000010000000000000000
00000000000000001000000000000000
00000000000000000100000000000000
00000000000000000010000000000000
00000000000000000001000000000000
00000000000000000000100000000000
00000000000000000000010000000000
00000000000000000000001000000000
00000000000000000000000100000000
00000000000000000000000010000000
00000000000000000000000001000000
00000000000000000000000000100000
00000000000000000000000000010000
00000000000000000000000000001000
00000000000000000000000000000100
00000000000000000000000000000010
00000000000000000000000000000001

Sample Output

1

Hint


Author

Source

The 8th UESTC Programming Contest Final