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.

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<1010000

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

Added by:Robert Gerbicz
Date:2009-04-06
Time limit:0.400s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 BASH BF CSHARP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Resource:classic, own input

hide comments
2018-12-15 16:32:06
BRUTE FORCE gave my python solution AC, weak test cases
2010-04-19 05:12:47 Ravi Kiran
@Pa1
This problem does require big int multiplication and you need to find a way to optimise the brute force approach so as to make as few computations as possible!
Hope this helps.
2009-08-19 10:02:12 ~ adieus ~
does it require a VFMUL ?

Re: No. And a brute-force approach is hard to get accepted likewise.

Last edit: 2009-12-22 07:00:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.