题目描述

第二类Stirling数$S(n, m)$表示将一个包含$n$个元素的集合划分为$m$个非空子集的方式数。例如，将四元素集划分为两部分有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(0, 0) = 1$；$S(n, 0) = 0$（当$n > 0$）；$S(0, m) = 0$（当$m > 0$）；
对于$n, m > 0$，$S(n, m) = m \cdot S(n - 1, m) + S(n - 1, m - 1)$。

本题任务：给定满足$1 \leq m \leq n$的整数$n$和$m$，计算$S(n, m)$的奇偶性（即$S(n, m) \mod 2$）。

示例

$S(4, 2) \mod 2 = 1$。

任务

为每个数据集编写一个程序，该程序需要：

读取两个正整数$n$和$m$， 计算$S(n, m) \mod 2$的值， 输出计算结果。

输入格式

第一行包含一个正整数$d$（$1 \leq d \leq 200$），表示数据集的数量。
接下来的$d$行，每行包含两个整数$n_i$和$m_i$（$1 \leq m_i \leq n_i \leq 10^9$）。

输出格式

输出$d$行，每行为$S(n_i, m_i) \mod 2$的结果（$0$或$1$）。

输入数据 1

1
4 2

输出数据 1

1

来源

中欧 2001