Erik: The Candyboy - 1

Erik has N candies, and he wants to distribute those candies among his friends. But he has more friends than the number of candies. So he wants to choose some(at least two) of his friends such that each of them gets at least one candy.
The satisfaction value of a friend is the number of candy he/she gets and the satisfaction value of Erik is the multiplication of his friends satisfaction values.

Who doesn't want more satisfaction? But Erik doesn't know how to achieve that.
So on behalf of Erik, you have to choose M friends to distribute all of N candies among them such that the ith friend gets Si satisfaction value and S1 × S2 ×...× SM is maximum.

Input

First line of input contains an integer T (1 ≤ T ≤ 100) — the number of test cases.
Each of next T lines contains an integer N (2 ≤ N ≤ 100) — the number of candy Erik has.

Output

For each test case, print the maximum satisfaction value Erik can achieve.

Sample

Input	Output
2 10 17	36 486
For N = 10, maximum satisfaction 36 will be achieved if you choose 3 friends and distribute candies among them in any of the following ways: {3, 3, 4} → 3 + 3 + 4 = 10, 3 × 3 × 4 = 36 {3, 4, 3} → 3 + 4 + 3 = 10, 3 × 4 × 3 = 36 {4, 3, 3} → 4 + 3 + 3 = 10, 4 × 3 × 3 = 36