徐老师的组队方案 1554

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：41 AC：0 Score：100

Description

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

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

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

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

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

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

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

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

Input

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

对于每组测试数据：

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

对于 $30\%$的数据，$1 \leq n \leq 10^2，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$

Output

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

Samples

input:

2 1 1 2 1

output:

1 0