在風(fēng)景如畫的藍(lán)橋村，n 名村民圍坐在一張古老的圓桌旁，參與一場(chǎng)思想的較量。這些村民，每一位都有著鮮明的身份：要么是譽(yù)滿鄉(xiāng)野的誠(chéng)實(shí)者，要么是無可救藥的說謊者。當(dāng)會(huì)議的鐘聲敲響，一場(chǎng)關(guān)于真理與謬誤的辯論隨之展開。每位村民輪流發(fā)言，編號(hào)為 i 的村民提出了這樣的斷言：坐在他之后的兩位村民——也就是編號(hào) i + 1 和 i + 2（注意，編號(hào)是環(huán)形的，所以如果 i 是最后一個(gè)，則 i + 1 是第一個(gè)，以此類推）之中，一個(gè)說的是真話，而另一個(gè)說的是假話。在所有搖曳不定的陳述中，有多少真言隱藏在謊言的面紗之后？

請(qǐng)你探索每一種可能的真假排列組合，并計(jì)算在所有可能的真假組合中，說謊者的總數(shù)。

輸入的第一行包含一個(gè)整數(shù) T，表示每次輸入包含 T 組數(shù)據(jù)。

接下來依次描述 T 組數(shù)據(jù)。

每個(gè)數(shù)據(jù)一行包含一個(gè)整數(shù) n，表示村落的人數(shù)。

2
3
3

6
6

【樣例說明】

在樣例中，可能的組合有「假，假，假」「真，真，假」「真，假，真」「假，真，真」，說謊者的總數(shù)為 3 + 1 + 1 + 1 = 6。

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

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

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

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