Sometimes solving a Diophantine equation is very hard. But, for example, the equation a+b²+c³+d⁴=n has a trivial solution for every value of n. Your task is to determine the number of solutions of the equation for each given n, assuming that in the equation all the values a, b, c and d are non-negative integers.

Input

The first line of input contains an integer T, representing the number of test cases (T<20000).

The following T lines contain one non-negative integer n each, where n < 10⁹.

Output

Output T lines, each containing the number of solutions of the respective equation for n.

Example

Input:
5
0
1
10
100
1000
Output:
1
4
19
148
1476