王老先生有快遞


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

王老先生有塊地,因為王老先生年輕時理財得當,所以這塊地的大小為 \(10^{100000}\) 平方單位。

今天他收到一份快遞,其中包含了 \(n\) 個正方形的植株,大小分別是 \(1\times 1, 2\times 2,..., n\times n\),王老先生想要把他的地劃分出一塊邊長為 \(k\) 的正方形 \(S\) 來種這些植株,種植的規則如下:

  1. 把長度為 \(n\) 的正方形植株種在 \(S\) 的左下角

  2. 逆時針依序將長度為 \(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
Notes

範測解答示意圖


Comments

There are no comments at the moment.