Description

有一個神秘的間諜組織，擁有 N = 2^k 名成員。為了防止成員身分曝光，他們皆以 k 位元的二進制字串來表示。

例如：

• 當 k=2 時，有四名成員分別表示為 00、10、11 和 01。
• 當 k=3 時，有八名成員表示為 000、100、110、010、001、101、111 和 011。

該組織的通訊協定規定：只有當兩位成員的二進制字串恰好只有一個位元不同時，才能直接傳送訊息 。若兩人間不能直接通訊，則需透過中介成員轉傳 。

相關定義如下：

• 傳送範例：當 k=3 時，成員 000 可以傳送訊息給成員 100、010 和 001 。
• 中介與跳躍：若兩名間諜希望通訊，可能需要其他成員作為中介。若訊息經過 t 個中介，則稱為 t+1 次跳躍。
• 距離 d(x,y)：定義為間諜 x 和 y 之間傳遞一則訊息所需的「最小跳躍次數」。例如，若 x=010 且 y=111，則 x 可先傳給 110 再傳給 111，故 d(x,y)=2。
• 傳遞範圍 R：定義為組織中任兩名不同成員之間距離的最大值，即 R = max{x,y}d(x,y)。

範例說明：

當 N=8（即 k=3）時，成員代號為 3 位元字串。 若 x=000 要傳給 y=111，最少需要經過 000 -> 001 -> 011 -> 111 共 3 次跳躍，故 R=3。

Input Format

• 第一行包含一個整數 q，表示測試資料的筆數。
• 接下來有 q 行，每一行代表一筆測試資料，每行包含一個整數 N。
• N 總是 2 的次方，且 1 <= N <= 2^30。

Output Format

• 對於每筆測試資料，輸出一行整數，代表該組織的傳遞範圍 R 。

Sample input & output

Input #1

2
2
2048

Output #1

1
11