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