Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2872
Binary Partitions

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Hadi loves binary numbers. So he likes to partition everything into powers of two. He wonders in how many ways he can partition a given number n into powers of two.

For example, there are 2 ways to partition 3: 1+1+1 and 1+2.

Help Him.

Input

The first line of input consists of a single integer T, the number of test-cases. Each test-case consists of a line containing n. (0 <= n <= 2,000,000)

Output

For each test-case, output a line containing number of ways in which n can be partitioned into binary numbers modulo 1,000,000.

Sample Input


4
1
2
3
280

Sample Output


1
2
2
93298


Author: Hadi Moshayedi
Source: AUT Contest 1
Submit    Status