Binary Stirling Numbers

The number of ways to partition a set of size $n$ into exactly $m$ non-empty subsets is called the Stirling number of the second kind, written $S(n, m)$.

For example, when $n = 4$ and $m = 2$ there are 7 ways:

• ${1,2,3} \cup {4}$, ${1,2,4} \cup {3}$, ${1,3,4} \cup {2}$, ${2,3,4} \cup {1}$
• ${1,2} \cup {3,4}$, ${1,3} \cup {2,4}$, ${1,4} \cup {2,3}$

$S(n, m)$ can be computed with the following recurrence:

• $S(0, 0) = 1$
• $S(n, 0) = 0 \quad (n > 0)$
• $S(0, m) = 0 \quad (m > 0)$
• $S(n, m) = m \cdot S(n-1, m) + S(n-1, m-1) \quad (n, m > 0)$

Given $n$ and $m$ with $1 \le m \le n$, write a program that prints $0$ if $S(n, m)$ is even and $1$ if it is odd.

The first line contains the number of test cases $D$ ($1 \le D \le 200$).

Each of the following $D$ lines contains one test case: two integers $n$ and $m$ separated by a space ($1 \le m \le n \le 10^9$).

For each test case, print $0$ if $S(n, m)$ is even or $1$ if it is odd, one result per line.