A. Niimmm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob decided to play the following game on a pile containing $$$n$$$ stones with Alice starting first :

  • On his/her turn, he/she will choose $$$2$$$ or $$$3$$$ stones from the pile and remove it.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent so they always play optimally.

You are the best friend of Alice. So add the minimum number of additional stones to the pile so that Alice will win.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each testcase contain single integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the number of stones in a pile.

Output

For each test case, print a single integer — minimum number of additional stones added to the pile so that Alice will win.

Example
Input
4
2
4
6
10
Output
0
0
1
2