You are Given a perfect Binary Tree with 10¹⁸ levels starting from level 1 and each level contains 2^level-1 Nodes. Nodes are numbered from 1.(see image for reference). Perfect binary tree with 5 levels:

You need to answer Q queries. Each query consists of a single number denoting a particular level of the given tree. You need the find the bitwise xor value of each element/number belonging to this particularly given level in the query. See sample input-output for clarity.

NOTE: Use Fast input-output like scanf and printf instead of cin, cout

INPUT

First Line consists of a single number Q  denoting the no. of queries.

Next, Q lines follow:

each line consists of a single no. L  denoting the level of the perfect binary tree.

OUTPUT

For each query print a single number on each line, i.e the required output to each query.

CONSTRAINTS

1<=Q<=10⁶

1<=L<=10¹⁸