Shubham owns a very big construction company in the town. But he builds very different types of buildings. By using a single brick a building of height 1 can be built. That is if 2 bricks are used then the height of the building will be 2 and so on. Now Shubham has N bricks and he wants to build buildings from that. But the Municipal corporation has imposed a new rule that the height of building should NOT be more than 3. You have to find the total number of possible combinations of buildings that can be built according to the new rule.
Lets say if Shubham has 3 bricks ,then the total number of possible combinations is 3.
1)3 buldings of height 1.
2)1 building of height 1 and 1 bulding of height 2.
1)1 building of height 3.
Note: All bricks are indentical.
Input format:
First line will contain T, the number of test cases. For each test case there will be a single line containing N.
Output format:
For each test case output a single line containing the number of possible combinations for that case.
Constraints:
1 <= T <= 105
1 <= N <= 109
For test case no 2,when bricks are 4 then the possible combinations are:
1)4 buildings of height 1
2)2 buildings of height 1 and 1 building of height 2
3)2 buildings of height 2
4)1 building of height 1 and 1 building of height 3
