대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

本题已重测。

描述

一个正整数如果能表示成两个正整数的平方差，则称这个数为“智慧数”。 例如 $16$ 等于 $5$ 的平方减去 $3$ 的平方，所以 $16$ 就是一个智慧数。 从 $1$ 开始的自然数列中，将“智慧数”从小到大编号为 $1,2,3,\cdots$ 现输入一个正整数 $n$，输出第 $n$ 个“智慧数”。

格式

输入

第一行一个整数 $T$，表示有 $T$ 次询问。 接下来每行一个整数 $n$，表示询问第 $n$ 个智慧数的值。

输出

输出 $T$ 行，每行对应询问的智慧数。

样例

1
5

9

2
5
9

9
15

说明

$T\le10000, \ n\le1000$