Hüsrar has just moved in to a new apartment, and she wants to decorate her living room. She likes turtles so she plans to hang some sort of abstract turtle shell pattern on her wall.

To create this turtle shell thingy, she combines equal-sized equilateral triangle shaped “shell fragments”. She wants the turtle shell thing to be in one piece, or in other words, she will make sure all the fragments are connected. Hüsrar is unsure how many shell fragments she wants to use. She is considering different arrangements of different numbers of these shell fragments but it is taking a lot of her time. Can you help her by telling her how many different shell designs are possible?

Two designs are considered equal if they can completely overlap after rotation and shifting (please notice that flipping is not included). The shell fragments connect by their edges as shown in the figure below:

Input

First line of input is the positive integer \(\mathbf{N}\), the number of test cases. The following \(\mathbf{N}\) lines include a single integer \(n_i\) , denoting how many shell fragments will be used for design \(i\).

Output

Total of \(\mathbf{N}\) lines, where in each line, print a single integer followed by a new line, the number of different possible turtle shells for design \(i\).

Constraints

• \(0 < N <= 100000\)
• 1 < \(n_i\) < 16

Example

Input

3
2
2
4

Output

1
1
4