Changu and Mangu are brothers. Changu likes 2 and Mangu likes 3. They decided to express each number as sum of 2 and 3.

They need your help. They want you to tell them the number of ways of writing a number as ordered sums of 2 and/or 3.

For example, there are 4 ways to write 8 as an ordered sum of 2s and/or 3s:

• 2 + 2 + 2 + 2
• 2 + 3 + 3
• 3 + 2 + 3
• 3 + 3 + 2

Input

The first line contains T, the number of test cases. It is followed by T lines, each containing the number N.

Output

You have to print the number of ways of writing N as ordered sum of 2 and/or 3. You have to print the answer mod 1000000007.

Example

Input:
3
2
3
8
Output:
1
1
4

Constraints:

T <= 100000

1 <= N <= 1000000