[中山市选2011]完全平方数

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌除 $1$ 以外的完全平方数，因为这些数看起来令他十分难受。因此，他也讨厌所有能被这些完全平方数整除的正整数。然而，这丝毫不影响他对其他数的热爱。

这天是小 X 的生日，小 W 想送给他一个数作为生日礼物。当然，他不能送一个小 X 讨厌的数。于是，小 W 列出了所有小 X 不讨厌的正整数，并选取其中第 $K$ 个数送给了小 X。小 X 很开心地收下了礼物。

然而，现在小 W 已经记不起自己送给小 X 的究竟是哪个数了。请你帮助他找出这个数。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$ ，表示测试数据的组数。

接下来 $T$ 行，每行包含一个整数 $K_i$ ，表示一组询问。

输出共 $T$ 行。

对于第 $i$ 组询问，输出第 $K_i$ 个无平方因子的正整数，即按从小到大的顺序，第 $K_i$ 个不存在整数 $d>1$ 使得 $d^2$ 整除它的正整数。

本题为中山市选 2011 试题「完全平方数」，题面与测试数据整理自 BZOJ。