Việc giải phương trình đại số Boolean với sự tham gia của các phép tính lô gic và xử lý bít khác khá xa với việc giải các phương trình đại số thông thường.

Để chứng minh cho điều đó, thầy giáo yêu cầu cả lớp về nhà xác định số lượng nghiệm không âm của từng phương trình trong số \(t\) phương trình, mỗi phương trình có dạng:

\(a-(a\oplus x)-x=0\)

trong đó:

• \(x\) là ẩn số,
• \(0 \le a < 2^{30}-1\),
• \(\oplus\) là phép tính \(XOR\).

Input

• Dòng đầu tiên chứa số nguyên \(t\ (1 \le t \le 1 000)\),
• Mỗi dòng trong \(t\) dòng sau chứa số nguyên \(a (0 \le a < 2^{30})\).

Output

• Đưa ra \(t\) số nguyên, mỗi số trên một dòng, số thứ \(i\) xác định số lượng nghiệm không âm của phương trình thứ \(i, i = 1 ÷ t\).

Example

3 
0 
2
1073741823

1 
2
1073741824