You are given a very simple problem, you need to evaluate the following function for a number of values of n.
F(0)=1
F(n) = F(n/2) + F(n/5) + F(n/7)

Input:
The first line contains number test cases T (T <= 100)
The next T lines contain a number n (n <= 10^9)

Output:
T lines each having values of F(n)

Sample I/O

Input
3
0
5
15

Output
1
9
21