이진 스털링 수

크기가 $n$인 집합을 공집합이 아닌 $m$개의 부분집합으로 나누는 방법의 수를 제2종 스털링 수(Stirling number of the second kind)라고 하며, $S(n, m)$으로 나타낸다.

예를 들어 $n = 4$, $m = 2$일 때는 다음과 같이 7가지로 나눌 수 있다.

• $\{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)$은 다음 점화식으로 계산할 수 있다.

• $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)$

$1 \le m \le n$을 만족하는 $n$과 $m$이 주어질 때, $S(n, m)$이 짝수이면 $0$을, 홀수이면 $1$을 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $D$가 주어진다. ($1 \le D \le 200$)

이후 $D$개의 줄에 각 테스트 케이스가 한 줄씩 주어진다. 각 줄에는 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le m \le n \le 10^9$)

각 테스트 케이스마다 $S(n, m)$이 짝수이면 $0$을, 홀수이면 $1$을 한 줄에 하나씩 출력한다.