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\le500$) ซึ่งระบุจำนวนกรณีทดสอบ สำหรับแต่ละกรณีทดสอบ:

บรรทัดแรกและบรรทัดเดียวมีจำนวนเต็ม $K$ ($K\le10^{18}$) ซึ่งระบุหมายเลขแถวที่ต้องการในสามเหลี่ยมปาสกาล

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงจำนวนจำนวนคี่ในแถวที่ $k$.

ตัวอย่าง

ข้อมูลนำเข้า 1

3
3
4
5

ข้อมูลส่งออก 1

2
4
2