يستعد Roundgod لخوض امتحان Gaokao (الامتحان الوطني الموحد للقبول في الجامعات والكليات العامة)، وجامعة أحلامه هي Zhejiang University. وأثناء دراسته للرياضيات، صادف مسألة مثيرة للاهتمام تتعلق بمثلث Pascal.

تعريف مثلث Pascal هو كما يلي:

العنصر الأول والعنصر الأخير في كل صف من مثلث Pascal يساويان $1$، والعنصر رقم $m$ في الصف رقم $n$ يساوي مجموع العنصرين رقم $m$ ورقم $m-1$ في الصف رقم $n-1$. وفيما يلي مثال لمثلث Pascal مكوّن من $5$ مستويات.

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

في المسألة، يُطلب من Roundgod حساب عدد العناصر الفردية في الصف رقم $126$ من مثلث Pascal.

بعد حلها، فكّر Roundgod في نسخة أصعب من هذه المسألة. وهو يوجّه إليك طلبات كثيرة لأسئلة مشابهة، لكن رقم الصف سيكون أكبر. احسب عدد العناصر الفردية في الصف رقم $k$ من مثلث Pascal.

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 500$)، يمثّل عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول والوحيد على عدد صحيح $K$ ($K \le 10^{18}$)، يمثّل رقم الصف المطلوب في مثلث Pascal.

الإخراج

لكل حالة اختبار، أخرج عدد الأعداد الفردية في الصف رقم $k$.

أمثلة

الإدخال 1

3
3
4
5

الإخراج 1

2
4
2