For an integer find the multiplicative digital root of it! Multiple all nonzero digits of that number and repeat this process until it is only a single digit. We call that digit the multiplicative digital root of the number. For example the multiplicative digital root of n = 2009 is 8, because the first iteration is: 2 × 9 = 18, the second is 1 × 8 = 8, and we stop here.

Input

The first line of the input file contains one integer T, the number of test cases. The following T lines each contains a big positive integer: n, where n < 10¹⁰⁰⁰⁰.

Output

Output the multiplicative digital root for each n.

Example

Input:
4
6
2009
555555555
847938630482747410708417738635300464477112059683336648877683

Output:
6
8
5
2