# 题目描述

有 $n$ 盏灯，编号从 $1$ 到 $n$，初始时灯全部亮着。进行 $n$ 轮如下操作：当进行第 $i$ 轮操作时，拉一遍所有编号为 $i$ 的倍数的灯的开关。要想使进行完 $n$ 轮操作后，恰好有 $k$ 盏灯亮着，则 $n$ 的最小值为多少？

# 输入格式

第一个数为数据组数 $t$ ($1 \le t \le 10^4$)

接下来 $t$ 行，每行一个整数 $k$ ($1 \le k \le 10^{18})

# 输出格式

对于每组数据，输出一行一个整数 $n$。

# 输入样例

3

1

3

8

# 输出样例

2

5

11

# 样例解释

当 $n = 5$ 时，最开始灯的状态是 $[1,1,1,1,1]$，$i = 1$ 时将 $1,2,3,4,5$ 反转，灯的状态变为 $[0,0,0,0,0]$，$i = 2$ 时将 $2, 4$ 反转，灯的状态变为 $[0,1,0,1,0]$，$i = 3$ 时将 $3$ 反转，灯的状态变为 $[0,1,1,1,0]$，$i = 4$ 时将 $4$ 反转，灯的状态变为 $[0,1,1,0,0]$，$i = 5$ 时将 $5$ 反转，灯的状态变为 $[0,1,1,0,1]$。最终剩下 $3$ 盏灯亮着，可以证明为了使得最终有 $3$ 盏灯亮着，$n$ 不可能小于 $5$。

# 题解：二分答案 + 数论

什么样的灯最后是灭的？被按了奇数次的灯。这意味着这个编号的正因数有奇数个。一般来讲因数是成对成对出现的，$i$ 是 $n$ 的因数，则 $\dfrac n i$ 也是 $n$ 的因数。那为什么会出现奇数个正因数？很显然，有一组 $i = \dfrac n i$ 的时候，也就是说这个数是完全平方数。

因此对于一个确定的 $n$，最后剩下的灯的个数 $k = n - \lfloor \sqrt n \rfloor$。现在我们有了 $k$，要反推回 $n$。

不难发现，当 $n$ 变大时，$k$ 也只增不减，也就是说，答案满足 单调性。于是我们便很自然地想到了二分答案，具体来说，二分这个 $n$ 的值，判断是否能满足 $\ge k$ 的要求，最终找到一个最小的 $n$ 即可。

在代码实现的过程中遇到了非常恶心的卡精度问题，具体写在参考代码的注释里了。

参考代码：

#include <stdio.h>

#include <math.h>

typedef long long ll;

ll Calc(ll ans)

{

    return ans - (ll)(sqrt(ans)); // 这里不要写成 ans - floor (sqrt (ans))，否则 long long - double 会出现很玄学的精度问题（被这个问题硬控了半个小时）

}

int main()

{

    // freopen("I.in", "r", stdin);

    // freopen("I.out", "w", stdout);

    int T;

    scanf("%d", &T);

    while (T -- )

    {

        ll k;

        scanf("%lld", &k);

        ll l = 1, r = 2e18;

        while (l < r)

        {

            ll mid = (l + r) >> 1;

            if (Calc(mid) >= k)

                r = mid;

            else

                l = mid + 1;

        }

        printf("%lld\n", l);

    }

    return 0;

}