FACTB12 - Factorial base 12

Once upon a time, in AAST training, a long contest was made, and too many solved FCTRL problem and didn't solve the much easier problems!!!!

So, their coaches gave them this problem to check if they understand the key idea of the problem or they just saw the solution before, this is very similar to FCTRL problem on spoj with a very small change.

You are given an integer, you have to output the number of trailing zeros of its factorial if it is represented by base 12.

Ex. 4! = 24 (base 10) = 20 (base 12), so there is one trailing zero in factorial 4 if it is represented by base 12.

Input

You are given an integer T (1<=T<=100000) the number of test cases, then T lines follow, each consists of an integer N (1<=N<=1000000000000000000).

Output

For each test case output one line which represents the number of trailing zeros of factorial n if it is represented by base 12.

Example

Input:
1
4

Output:
1

Added by:Walid Amin
Date:2016-04-24
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2019-05-02 19:50:58
if it is impossible to find any ans... what should we print ??
2018-02-16 09:54:24
10 = 2 x 5, 12 = 2 x 2 x 3
2016-11-21 12:19:50
Sorry for spamming WAs. Anyways thanks for the problem, just discovered a little truth behind the so-called base numbers.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.