P4101 [HEOI2014] Everyone Says Jiangnan Is Good

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.

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

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