Description

Xiao Z is a hardcore ZRP (Zealot Round-game Player), and he recently recalled a game he played in Jiangnan when he was a child.

In the past, people would compose lyrics while playing games. For example, this piece “Pusaman (Púsà Mán)” was written by Wei Zhuang while playing: 人 人 尽 说 江 南 好， 游 人 只 合 江 南 老。

However, today we are not very concerned about what people wrote. We only care about the game that Xiao Z played. The rules are as follows: there are $n$ piles of stones, each initially having $1$ stone. Xiao Z and his friend take turns, and Xiao Z moves first. A move can merge any two piles into one pile. Whoever cannot move loses.

However, if a pile becomes too high, it might be dangerous. Therefore, they agreed that at any time, the number of stones in any pile cannot exceed $m$. That is, if there are two piles with $a$ and $b$ stones and $a + b > m$, then these two piles cannot be merged.

Xiao Z and his friend are very smart, so they always choose optimal strategies. Now Xiao Z wants to know, given $n$ and $m$, who will win.

Input Format

This problem contains multiple test cases. The first line contains a single integer $T$, the number of test cases.

Each of the following $T$ lines contains two positive integers $n, m$.

Output Format

Output $T$ lines, each being $0$ or $1$. If it is $0$, it means Xiao Z (the first player) will win. If it is $1$, it means the second player will win.

5
7 3
1 5
4 3
6 1
2 2

1
1
1
1
0

Hint

For $10 \%$ of the testdata, $m \ge n$.
For $20 \%$ of the testdata, $n, m \le 10$.
For $30 \%$ of the testdata, $n, m \le 50$, $2 \cdot m \ge n$.
For $50 \%$ of the testdata, $n, m \le 100$.
For $70 \%$ of the testdata, $n, m \le {10}^6$.
For $100 \%$ of the testdata, $1 \le n, m \le {10}^9$, $1 \le T \le 100$.

Translated by ChatGPT 5