Monocarp has three nephews. New Year is coming, and Monocarp has $n$ candies that he will gift to his nephews.

To ensure that none of the nephews feels left out, Monokarp wants to give each of the three nephews the same number of candies.

Determine the minimum number of candies that Monocarp needs to buy additionally so that he can give each of the three nephews the same number of candies. Note that all $n$ candies that Monocarp initially has will be given to the nephews.

Input

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 100$) — the number of candies that Monocarp initially has.

Output

For each test case, print one integer — the minimum number of candies that Monocarp needs to buy additionally so that he can give each of the three nephews the same number of candies.

Note

In the first example, Monocarp needs to buy $2$ candies. After that, he will have $9$ candies, and he can give each of the three nephews $3$ candies.

In the second example, Monocarp does not need to buy any candies, as he initially has $24$ candies, and he can give each of the three nephews $8$ candies.

Samples

2
7
24

2
0