You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个环由 $n$ 个元素组成，顺时针标号为 $1$ 至 $n$，其中 $n$ 为不小于 $\mathbf{4}$ 的偶数。每个元素都有一个颜色，且第 $i$ 个元素的颜色居下列二者之一：

1. 除元素 $i$ 外的其他元素均与 $i$ 不同色，Alice 称元素 $i$ 为「独立」的；
2. 除元素 $i$ 外有且仅有元素 $i + \frac n 2$ 或 $i - \frac n 2$（其中恰有一个在编号范围内）与 $i$ 同色，Alice 称元素 $i$ 为「对立」的。

定义一个环的色彩值为所有被「对立」元素分开的子段的长度乘积。换言之，将所有的「对立」元素移除，色彩值等于剩余的环上连续子段（包括长度为 $0$ 的子段 —— 出现在两个「对立」元素相邻的情况下）的长度乘积。特别地，如果环上没有「对立」元素，那么其色彩值为 $0$。

一个 $n=18$ 的例子。移除「对立」元素后剩余的子段有 {2}, {4,5,6}, {8,9},{11},{13,14,15},{17,18} 
，其色彩值为 $1 * 3 * 2 * 1 * 3 * 2 = 36$

有些颜色似乎很像…… 不过确实是不同的。

现在 Alice 想获得一个色彩值 不小于 $m$ 的环。Alice 想请你帮忙计算这样一个环的最小大小 —— Alice 仍旧犹豫不定，因此你需要对于 $T$ 个这样的 $m$ 分别进行计算。

输入格式

输入的第一行包含一个正整数 $T$ —— 需要计算的 $m$ 的个数。

接下来 $T$ 行，每行包含一个正整数 $k$ —— 由于 $m$ 可能很大，输入的值表示它的正平方根，即 $m = k^2$。

输出格式

输出 $T$ 行 —— 对于每个输入的 $k$ 输出一行，包含一个整数，表示色彩值不小于 $k^2$ 的环最少包含的元素个数。当然啦，一定是个偶数。

4
5
10
221
1317

12
18
40
54

$k=5$ 即 $m=25$

$k=10$ 即 $m=100$。这个色彩值为 144。

数据范围

对于所有数据，有 $1 \leq k \leq 10^{18}$，$1 \leq T \leq 10^6$。