{"raw_statement":[{"iden":"statement","content":"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:\n\nDavid 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')_). \n\nThe first line of input contains a single integer $n$ ($1 <= n <= 10^5$), representing the number of games that David and David will play.\n\nEach of the next $n$ lines contains three space-separated integers $x$, $y$, and $k$ ($0 <= x, y <= 10^9$; $0 <= k <= 12$), representing a game with a tolerance $k$ that starts with a pile of $x$ stones and a pile of $y$ stones.\n\nThe 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. \n\n"},{"iden":"input","content":"The first line of input contains a single integer $n$ ($1 <= n <= 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 <= x, y <= 10^9$; $0 <= k <= 12$), representing a game with a tolerance $k$ that starts with a pile of $x$ stones and a pile of $y$ stones."},{"iden":"output","content":"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. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of games.  \nFor each game $ i \\in \\{1, \\dots, n\\} $, let $ (x_i, y_i, k_i) \\in \\mathbb{Z}_{\\ge 0}^3 $ denote the initial state, where:  \n- $ x_i, y_i $ are the sizes of pile 1 and pile 2,  \n- $ k_i $ is the tolerance parameter.  \n\n**Moves**  \nFrom a state $ (x, y) $, a player may move to:  \n- $ (x - a, y - b) $, where $ a, b \\in \\mathbb{Z}_{\\ge 0} $, $ a + b \\ge 1 $, and $ |a - b| \\le k $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 0 \\le x_i, y_i \\le 10^9 $  \n3. $ 0 \\le k_i \\le 12 $  \n\n**Objective**  \nFor each game $ i $, determine the winner under optimal play, assuming David (Player 1) moves first:  \n- Output $ 1 $ if the first player has a winning strategy.  \n- Output $ 2 $ if the second player has a winning strategy.  \n\nThe game is impartial; the outcome depends only on the state $ (x, y) $ and $ k $.","simple_statement":"Two piles of stones, x and y. Players take turns. On each turn, a player can remove any number of stones from one pile, but must leave at least max(0, a - k) stones in that pile, where a is the current number of stones. First player wins if they can force a win, else second wins. Output 1 for first player win, 2 for second.","has_page_source":false}