SP4172 DROOT - Multiplicative digital root

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.

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_

Output the mulplicative digital root for each n.