Problem Description

Codu wants to travel from City A to City B. There are N stations between A and B. There Are 3 kinds of trains that runs from every station.

Train 1- Stops at every station

Train 2- Stops at every alternate station

Train 3- Stops at every third station

Codu can use any combination of the trains to reach from City A to City B. However, he cannot travel in the reverse direction during the course of his travel. He is allowed to change as many train as needed to reach the station.

You need to find how many ways Codu can reach City B from City A.

Constraints

1 <= T <= 5

0 < = N <=10^2

Input

First line contains an integer T denoting the number of test cases.

Next T lines contains an integer N denoting the number of stations between A and B for each test case.

Output

For each test case print, no of combination in A new line

Examples

Example

Input

2

0

1

Output

1

2

Explanation

For 0: No station between A and B. So only possible way to travel is by train 1.

For 1: There is 1 station between A and B. So, Codu has two ways to travel. First way is to travel by train 1 which halts at every station. Second way is to travel by train 2 which starts from A directly stops at B.