题目描述

面条老师 最近在玩一个很有趣的联机游戏，这个游戏允许 面条老师 在线和其他玩家组队挑战 $BOSS$。

对于不同难度的 $BOSS$，团队人数限制也不同。

面条老师 是一个迷信的人，他总是认为奇数比较吉利而偶数不吉利

现在除他以外的在线人数是 $N$ ，他希望在这 $N$ 个人中挑选 $K$ 个人和他组成团队去挑战一个 $BOSS$

而他认为如果可选组队方案总数是奇数的话就能挑战成功，若可选组队方案总数是偶数的话就会挑战失败。

当然他认为如果选的是 $(1,2,3),(2,1,3),(3,2,1)$ 等都属于同一个方案

但是 面条老师 的数学学的不好，所以请你帮助他计算一下，他能否挑战成功。

若能成功则输出 1，若不能成功则输出 0

输入格式

输入第一行为 $T$ 表示有 $T$ 组测试数据

对于每组测试数据：

接下来的每一行包含两个非负整数 $N$ 和 $K$(保证 $K \leq N$)

输出格式

输出共 $T$ 行，对于每组测试数据，若能挑战成功则输出 1 若会挑战失败则输出 0

2
1 1
2 1

1
0

提示

面条老师 一拍脑门 突然想到n个人里面挑选k个人，方案数为$C(n,k)$

$C(n,k)=\frac{n!}{k! * (n-k)!}$

但是 煎饼老师 大喊一声，跳了出来，又一拍 面条老师 的脑门说道“动动你的脑子，你看看数据规模，你这$C(n, k)$算的出来么！”

数据规模与约定

对于 $30\%$的数据，$1 \leq n \leq 10，T \leq 10^4$

对于 $50\%$的数据，$1 \leq n \leq 10^3，T \leq 10^5$

对于 $100\%$的数据，$1 \leq n \leq 10^9，T \leq 10^5$