406234: GYM102319 D David vs David

David and David are playing a game. This game is played with two piles of stones, which we name pile 1 and pile 2. First, David and David decide on some non-negative number $$$k$$$ which is called the tolerance. Then, David and David take turns making moves with David going first, and whoever cannot make a move loses. Each move is one of the following:

1. Remove any positive number of stones from one of the two piles
2. Remove $$$a$$$ stones from pile 1 and $$$b$$$ stones from pile 2, where $$$|a-b|\le k$$$ and $$$a,b>0$$$

David and David will play $$$n$$$ games with different starting configurations. They want to check whether they played optimally, so for each game, they want you to tell them who should win with optimal play (and the answer is not print('David')).

The first line of input contains a single integer $$$n$$$ ($$$1\le n\le 10^5$$$), representing the number of games that David and David will play.

Each of the next $$$n$$$ lines contains three space-separated integers $$$x$$$, $$$y$$$, and $$$k$$$ ($$$0\le x,y\le 10^9$$$; $$$0\le k\le 12$$$), representing a game with a tolerance $$$k$$$ that starts with a pile of $$$x$$$ stones and a pile of $$$y$$$ stones.

The output should contain $$$n$$$ lines, each containing one integer. For each game, in the order given in the input, output a $$$1$$$ if the first player wins, and a $$$2$$$ if the second player wins.

15
0 0 0
23 9 1
97 99 2
1984 6 3
277 348 4
2384 19 5
138 19 6
123 372 7
112 1021 8
99328 9702 9
3172 283401 10
1937 23405 11
421443 503539 12
508320368 822479633 0
924717293 228947159 1

2
2
1
1
1
1
2
1
2
1
1
2
1
2
1