**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.

#check if this is correct

def trainWays(n):

if n == 0:

return 1

elif n >= 1:

return 1 + trainWays(n-1)

elif n >= 2:

return 2 + trainWays(n-1)