Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Erik: The Candyboy - 1

By skmonir · Limits 1s, 512 MB

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

InputOutput
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


Discussion

Statistics


86% Solution Ratio

AbuBokorEarliest, 3w ago

AbuBokorFastest, 0.0s

AbuBokorLightest, 131 kB

MehrabShortest, 278B

Submit

Login to submit