Migrated from Lutece 118 Love is Persistence

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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\leq 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.

Samples

Resources

The 8th UESTC Programming Contest Final