Roundgod עומד לגשת ל־Gaokao (הבחינה הלאומית האחידה לקבלה לאוניברסיטאות ולמכללות כלליות), ומוסד הלימודים שעליו הוא חולם הוא Zhejiang University. בזמן שהוא לומד מתמטיקה, הוא נתקל בבעיה מעניינת הקשורה למשולש פסקל.

ההגדרה של משולש פסקל מובאת להלן:

האיבר הראשון והאיבר האחרון בכל שורה במשולש פסקל הם $1$, והאיבר ה־$m$ בשורה ה־$n$ שווה לסכום האיבר ה־$m$ והאיבר ה־$(m-1)$ בשורה ה־$(n-1)$. הנה דוגמה למשולש פסקל בעל 5 שורות.

$$ \begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1 \end{array} $$

במשימה, Roundgod נדרש לחשב כמה מהאיברים בשורה ה־$126$ של משולש פסקל הם מספרים אי־זוגיים.

לאחר שפתר זאת, Roundgod חושב על גרסה קשה יותר של הבעיה. הוא נותן לכם בקשות רבות עם שאלות דומות, אך מספר השורה יהיה גדול יותר. חשבו כמה מהאיברים בשורה ה־$k$ של משולש פסקל הם מספרים אי־זוגיים.

קלט

יש מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 500$), המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:

השורה הראשונה והיחידה מכילה מספר שלם $K$ ($K \le 10^{18}$), המציין את מספר השורה המבוקשת במשולש פסקל.

פלט

עבור כל מקרה בדיקה, הדפיסו את מספר המספרים האי־זוגיים בשורה ה־$k$.

דוגמאות

קלט 1

3
3
4
5

פלט 1

2
4
2