Slime and Stones

Problem Description

Orac and Slime are playing a game. There are two groups of stones, the first group contains $a$ stones and the second contains $b$ stones. Orac and Slime operate them by turns in the game. For each operation, they have two choices:

1. Pick up any number of stones from a certain group;
2. Pick up $x$ stones from the first group and $y$ from the second group, which $x,y$ satisfy $|x-y|\le k$. $k$ is a given constant. Notice that not picking up any stone in an operation is not allowed. If there is no stone left in both groups at the beginning of one's turn, he loses the game. Orac would like to know whether there exists a winning strategy for him if he operates first. They will play many times, so he will make multiple queries.

Input

The first line contains one integer $T$($1\le T\le 10^5$), which stands for the number of queries that Orac makes. In the following $T$ lines, each line contains three integer $a,b,k$($1\le a\le 10^8, 1\le b\le 10^8, 0\le k\le 10^8$).

Output

The output contains $T$ lines, with an integer $0$ or $1$ in each line, stand for there exist/not exist a winning strategy for the given situation.

Sample Input

4
1 2 0
2 4 0
1 2 1
2 6 1

Sample Output

0
1
1
0

Hint

In the first query, if Orac picks up all the stones from a group, Slime will pick up all the stones from the other group, and if Orac picks up a stone from the second group, Slime will pick up a stone from both groups.

Source

2020 Multi-University Training Contest 9