1123 - ProjectEuler 12
描述

输入一个自然数n。问最小的,包含大于n个约数的三角数,是多少。

所谓三角数,是形如i*(i+1)/2的数,比如1,3,6,10,15,21,28,……

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28


输入

第一行输入组数T, 接下来T行,每行一个整数n。 (1 <= T <= 50,0 <= N <= 500)


输出

对于每组数据,输出一个三角数,表示答案。


样例

输入

6
0
1
2
3
4
500

输出

1
3
6
6
28
76576500
提示

一个有 500 个约数的数字,可能很大,如果我们逐一计算所有三角数的约数数量 d(n) ,可能会出现超时。
实际上我们可以利用三角数的某些特性,快速的计算 d(n) (d(n)指的是约数的数量)。 
F(n)=i∗(i+1)/2 。
 而 i 同 i+1 是互质的。 
如果 i 是偶数, i/2 与 i+1 互质。
 如果 i 是奇数, i 与 (i+1)/2 互质。
 如果 2 个数是互质的,那么 d(i∗j)=d(i)∗d(j) ,所以我们只需要预处理出较小范围内,每个数的约数,就可以快速计算三角数的约数数量。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1