王老先生有快遞
王老先生有塊地,因為王老先生年輕時理財得當,所以這塊地的大小為 \(10^{100000}\) 平方單位。
今天他收到一份快遞,其中包含了 \(n\) 個正方形的植株,大小分別是 \(1\times 1, 2\times 2,..., n\times n\),王老先生想要把他的地劃分出一塊邊長為 \(k\) 的正方形 \(S\) 來種這些植株,種植的規則如下:
把長度為 \(n\) 的正方形植株種在 \(S\) 的左下角
逆時針依序將長度為 \(n-1\) 至長度為 \(1\) 的正方形植株放入 \(S\) 中,其中要滿足:
(1) 沒有任何正方形植株相互重疊
(2) 長度相差為 \(1\) 的植株需相鄰,也就是說兩個正方形植株各有其中一邊部分重疊
(3) 為了這塊地的美觀,每一個植株皆需有一邊貼在 \(S\) 上
請問王老先生最小需要切出多長的正方形土地?
Input
第一行包含一個正整數 \(T\),代表測資的筆數。
接下來 \(T\) 行皆包含一個正整數 \(n\),代表該筆測資中正方形的植株數 \(n\)。
\(1\leq T\leq 1000, 1\leq n\leq 10^9\)
Output
輸出 \(T\) 行,其中第 \(i\) 行代表第 \(i\) 筆測資中 \(k\) 的最小值。
Constraints
第 \(1\) 組測資,\(n\leq 9\)。 (\(9 \%\))
第 \(2\) 組測資,\(\Sigma n\leq 100\)。 (\(24 \%\))
第 \(3\) 組測資,\(\Sigma n\leq 2\cdot 10^5\)。 (\(23 \%\))
第 \(4\) 組測資,無特別限制。 (\(44 \%\))
Sample Input 1
2
7
9
Sample Output 1
13
21
Comments