在一場(chǎng)智力對(duì)弈的游戲中，兩位玩家小藍(lán)和小喬需要對(duì)一個(gè)初始值均為 0、大小為 n × n 的矩陣進(jìn)行操作，以展現(xiàn)他們的智慧和謀略，并確定誰才是最強(qiáng)的策略家。操作規(guī)則如下：

? 小藍(lán)擁有先手操作權(quán)，完成操作后輪到小喬，然后再輪到小藍(lán)，依此規(guī)律交替進(jìn)行。? 在小藍(lán)的每個(gè)回合中，他可以選擇矩陣中的 2 個(gè)元素，并將這些元素的值變更為 1。

? 在小喬的第 1 個(gè)回合中，他可以選擇一個(gè)大小為 1 × 1 的子矩陣，并將該子矩陣內(nèi)的所有元素的值重置為 0。在小喬的第 2 個(gè)回合中，他可以選擇一個(gè) 2 × 2 的子矩陣，并將該子矩陣內(nèi)的所有元素的值重置為 0。以此類推，在小喬的第 i 個(gè)回合中，他可以選擇一個(gè)大小為 i × i 的子矩陣，并將該子矩陣內(nèi)所有元素的值重置為 0。

? 在雙方各進(jìn)行了 n 次操作后，游戲結(jié)束。

設(shè)在整個(gè)游戲過程中，矩陣中值為 1 的元素的數(shù)量最多時(shí)為 X。

小藍(lán)致力于最大化 X 的值，小喬致力于最小化 X 的值。

假設(shè)兩位玩家都具有完美的邏輯推理能力，并總是采取最佳策略。請(qǐng)問，X的值會(huì)是多少（即在整個(gè)游戲過程中，矩陣中值為 1 的元素的數(shù)量最多時(shí)是多少）？

輸入的第一行包含一個(gè)整數(shù) T，表示數(shù)據(jù)的組數(shù)。接下來 T 行，每行包含一個(gè)整數(shù) n，表示矩陣的大小。

對(duì)于每組數(shù)據(jù)，輸出一行包含一個(gè)整數(shù)，表示答案。

2
2
5

3
5

【樣例說明】

在第一個(gè)樣例中，小藍(lán)和小喬需要輪流操作一個(gè) 2 × 2 的矩陣。

初始矩陣狀態(tài)：

| 0 0 |

| 0 0 |

小藍(lán)的第 1 個(gè)回合：將兩個(gè)值為 0 的元素變更為 1。可能的狀態(tài)為：

| 1 1 |

| 0 0 |

小喬的第 1 個(gè)回合：小喬只能選擇一個(gè) 1 × 1 的子矩陣將元素重置為 0。為了最小化值為 1 的元素?cái)?shù)量，小喬需要將已經(jīng)是 1 的一個(gè)元素重置為 0?？赡艿臓顟B(tài)為：

| 0 1 |

| 0 0 |

小藍(lán)的第 2 個(gè)回合： 小藍(lán)再次將兩個(gè)元素值為 0 的元素變更 1?？赡艿臓顟B(tài)為：

| 1 1 |

| 1 0 |

小喬的第 2 個(gè)回合： 小喬可以選擇一個(gè) 2 × 2 的子矩陣（即整個(gè)矩陣），并且把所有值重置為 0。 

| 0 0 |

| 0 0 |

因此，在雙方都采取最佳策略下，矩陣中值為 1 的元素最多時(shí)能達(dá)到 3 個(gè)。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ T ≤ 10³，1 ≤ n ≤ 10³。

對(duì)于所有評(píng)測(cè)用例，1 ≤ T ≤ 10⁵，1 ≤ n ≤ 10⁹。