Description

五一七天假期，小明的爸爸妈妈出门已经旅游去了，家里只剩下小明和她姐姐。作为一个孩子，小明当然不能忘了玩游戏了，趁姐姐在做饭她便偷偷的跑出来拿起姐姐的手机开始玩游戏。（关于解锁手机问题我也很好奇，但是不重要，哈哈哈）看到姐姐手机里还没结束的游戏，小明决定继续下去。

此关游戏是一个划分数字的游戏。给你一个数字n，小明可以随性选中一个数p（1 <p <= n），将n拆分成x =n/p和y = n-x;并对x，y继续重复这个过程，直到他有了n个1.但是这个过程是要记分的，想通过此关必须要得到最多的分数!!!

所以规定在每次小明进行划分时，会给小明奖励u * v的分数，小明希望你能帮他最大化他的得分。

Format

Input

第一行输入一个数字T，表示有T次询问

接下来便有T个n，输出n可划分的最大得分

（1<n<1e9)

Output

输出最大分数的值

Samples

1
5

10

Hint