Abhishek popularly known as "Gutts" by his friends Anurag garg and Bhavik, is very good at solving logical problems. Recently he was solving some encryption problem and challenges Bhavik to solve the same.Bhavik being lazy asks for your help to encrypt the numbers using some test cases given by "Gutts";

your task is to find the encypted numbers for the input numbers:

Input

Input contains several numbers each in a different line 

first line contains T : number of test cases (T <= 100)
For next T lines each line contains a number n (0<=n<2^64)

Output

For every test case print encrypted number in separate line .

Input:
6

2

3

6

7

17

25

Output:
0

1

1

3

8

9

NOTE: for each test case ans will be less than 2^64