During the time of the festival of lights (Diwali), Mr. Seth asks people of an unknown village to switch off the lights of all the houses in the village. Mr. Seth wanted to light the village with the help of a lighted special candle. The village occupies an area of a square of n units side.
The property of the candle is that it can light:
- The immediate leading row house.
- The immediate leading column house.
- The immediate leading diagonal house.
- All or any order from the above three depending upon the situation.
Note: Each house in the village occupies 1 X 1 sq. units. (i.e. total house is equal to area of the village).
Now help the village people in finding the minimum number of candles required to light the whole village.
Input Format
1. The first line contains an integer T describing the number of testcases.
2. Each line of the T cases has an integer N describing the one side of the village.
Output Format
For each testcase, print the minimum number of candles required to light the village.
Constraints
- 1 <= T <= 1000
- 1 <= N <= 10000
In the first test case N=2 so the area of the village is 4 sq. units and no. of houses = 4. Hence 1 candle can light the village.
Village = [[H H], [ H H ]] If the candle is at 1st house i.e. position 0,0 of the Village then by candle property it can light all houses.
Similarly, for the second test case, only 6 candles can light the total 36 houses of the village.
