Dr. Patel đang loay hoay nghiên cứu toán học để đạt được điểm cao nhất trong bài luận án của mình. Dr. Patel đang nghiên cứu như sau.

Với một số ~N~. Tìm số lượng số ~X~ thoả mãn:

• ~0 \leq X \leq N~.
• ~N + X = N \oplus X~.

(với phép toán ~\oplus~ là phép toán XOR trong các phép toán thao tác bit).

Ví dụ: Với ~N = 5~ ta có ~2~ giá trị của ~X~ là ~[0, 2]~ thoả mãn điều kiện trên.

• ~5 + 0 = 5,\ \ 5 \oplus 0 = 5~
• ~5 + 2 = 7,\ \ 5 \oplus 2 = 7~

Dr. Patel mời bạn về để nghiên cứu cùng ông ấy, hãy giúp ông ấy tính toán xem, với ~N~ có bao nhiêu giá trị của ~X~ thoả mãn điều kiện trên.

Input

• Dòng đầu tiên mỗi dòng chứa 1 số nguyên ~T~ là số bộ test ~(1 \leq T \leq 10^5)~.
• Ứng với mỗi test, mỗi dòng chứa 1 số nguyên dương ~N~ ~(1 \leq N \leq 10^{16})~.

Output

• Với mối test, in ra số lượng ~X~ thoả mãn yêu cầu đề bài.

Sample

Input #1

5
10
8
88
31
2

Output #1

Case #1: 4
Case #2: 8
Case #3: 16
Case #4: 1
Case #5: 2

Giải thích #1

Với trường hợp ~N = 10~, có ~4~ trường hợp ~X~ thoả mãn điều kiện đề bài:

• ~10 + 0 = 10,\ \ 10 \oplus 0 = 10~
• ~10 + 1 = 11,\ \ 10 \oplus 0 = 11~
• ~10 + 4 = 14,\ \ 10 \oplus 0 = 14~
• ~10 + 5 = 15,\ \ 10 \oplus 0 = 15~

Với trường hợp ~N = 2~, có ~2~ trường hợp ~X~ thoả mãn điều kiện đề bài:

• ~2 + 0 = 2,\ \ 2 \oplus 0 = 2~
• ~2 + 1 = 3,\ \ 2 \oplus 1 = 3~