考慮對一個正整數\(x\)進行操作，如果他是奇數時變成 \(3x+1\)，是偶數時變成 \(x/2\)。

角谷猜想宣稱，每一個正整數一定會經過有限次操作後回到 \(1\)，從此在 \(1,4,2,1\) 循環。

我們稱一個數是『燒雞數』，如果他在這個過程中從來沒有超過 \(N\)。

試求有幾個燒雞數

Input

第一行一個整數 \(T\)，代表測資筆數

\(T \le 50\)

一行一個整數 \(N\)

\(4\le N \le 10^9\)

Output

有幾個燒雞數

Constraints

第 \(1\) 組測資, \(N\le 10\)。 \((20\text{%})\)

第 \(2\) 組測資, \(N \le 1000\)。\((20\text{%})\)

第 \(3\) 組測資, \(T = 1, N\le 5\times 10^7\)。\((20\text{%})\)

第 \(4\) 組測資, \(N \le 5\times 10^7\)。\((20\text{%})\)

第 \(5\) 組測資, 沒有其他限制。\((20\text{%})\)

Sample Input

1
8

Sample Output

4

滿足的數有 \(1,2,4,8\)