Time Limit: 1.0 s

Memory Limit: 128.0 MB

Description

Alice and Bob are engaged in a game known as XOR LOVE. In this game, Alice presents Bob with a number and tasks him with calculating the XOR of consecutive numbers from 0 to that given number, inclusive. Despite Bob's efforts, he's encountered difficulty in finding the solution to win the game. Seeking assistance, he turns to you as a trusted friend for help in securing victory. Could you assist Bob in solving this challenge and emerging victorious in the game?

Format

Input

The first line of the input contains one integer \(t\) \((1 <= t <= 10^5)\) - the number of test case.
Each of the following line contains the number \(n\) \((1 <= n <= 10^9)\)

Output

For each test case print the answer.

Sample 1

Input

2
1
4

Output

1
4