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:
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 <= 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.
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.
## Input
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.
## Output
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.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of games.
For 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:
- $ x_i, y_i $ are the sizes of pile 1 and pile 2,
- $ k_i $ is the tolerance parameter.
**Moves**
From a state $ (x, y) $, a player may move to:
- $ (x - a, y - b) $, where $ a, b \in \mathbb{Z}_{\ge 0} $, $ a + b \ge 1 $, and $ |a - b| \le k $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 0 \le x_i, y_i \le 10^9 $
3. $ 0 \le k_i \le 12 $
**Objective**
For each game $ i $, determine the winner under optimal play, assuming David (Player 1) moves first:
- Output $ 1 $ if the first player has a winning strategy.
- Output $ 2 $ if the second player has a winning strategy.
The game is impartial; the outcome depends only on the state $ (x, y) $ and $ k $.