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 mulplicative digital root for each n.

Example

Input:
4
6
2009
555555555
847938630482747410708417738635300464477112059683336648877683

Output:
6
8
5
2

Warning: large input data, be careful with certain languages

Warning: not every languages are available for this task