Migrated from Lutece 480 Sumsets

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of $2$. Here are the possible sets of numbers that sum to $7$:

1. $1+1+1+1+1+1+1$
2. $1+1+1+1+1+2$
3. $1+1+1+2+2$
4. $1+1+1+4$
5. $1+2+2+2$
6. $1+2+4$

Help FJ count all possible representations for a given integer $N$ ($1\leq N\leq 1,000,000$).

Input

The first line of standard input contains $t$($t\leq 1000$), the number of test cases.For each case, there is a single line with a single integer, $N$.

Output

For each each case ,output a line with the number of ways to represent $N$ as the indicated sum. Due to the potential huge size of this number, print only last $9$ digits (in base $10$ representation).

Samples

2
7
8

6
10

Resources

2011 UESTC ACM Training for Math