4477 . 青蛙和他的青蛙下蛋
Description
青蛙，顧名思義，他是一隻青蛙
一隻青蛙會做青蛙會做的事
例如下蛋(吃)
現在青蛙想喝青蛙下蛋
此時社辦的新桌子上有\(n\)杯青蛙下蛋
每杯青蛙下蛋中剛開始各有1顆青蛙蛋
而你，作為學弟，為了爭奪躺在社辦沙發上的權利，只好接受青蛙的要求，幫他調出好喝的青蛙下蛋
當然，調出好喝的青蛙下蛋不是那麼容易的事
青蛙將調出好喝青蛙下蛋的方式定義為使桌上的飲料杯數最少，然而，將兩杯飲料倒在一起也不能亂倒，必須要每次取兩杯青蛙蛋數量相等的飲料才會是好喝的倒法
為了爭奪沙發的使用權利，你自然是完美的調出了好喝的青蛙下蛋，但現在又有一個問題了，除了青蛙以外，其他人也想喝好喝的青蛙下蛋，因此請問你一共調出了幾杯青蛙下蛋呢？
Input Format
每筆輸入檔包含\(t\)筆測資
第一行為一個整數t，代表該筆輸入檔有\(t(1 \leq t \leq 10^5)\)筆測資
每筆測資佔一行
每筆測資各有一個整數\(n(1 \leq n \leq 10^9)\)，意義如同題敘
Output Format
對於每筆測資輸出答案並換行
Sample Input 1
2
4
6
4
6
Sample Output 1
1
2
2
Hints
範例測資說明
\(n = 4\)時，以下是一種合併方式
{1, 1, 1, 1}合併第1, 4杯
{2, 1, 1}合併第2, 3杯
{2, 2}合併第1, 2杯
{4}剩下一杯飲料
\(n = 6\)時，以下是一種合併方式
{1, 1, 1, 1, 1, 1}合併第1, 4杯
{2, 1, 1, 1, 1}合併第4, 5杯
{2, 1, 1, 2}合併第1, 4杯
{4, 1, 1}合併第2, 3杯
{4, 2}沒有剩下青蛙蛋數相同的飲料了，還剩下兩杯
我們可以證明沒有更好的合併方式
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 100 |
