7591: Slime and Stones

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|≤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.

The first line contains one integer T (1≤T≤105 ), which stands for the number of queries that Orac makes.
In the following T lines, each line contains three integer a,b,k (1≤a≤108,1≤b≤108,0≤k≤108 ).

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.

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

0
1
1
0