该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

大维最近在玩一个很有趣的联机游戏，这个游戏允许大维在线和其他玩家组队挑战强大的 BOSS。对于不同难度的 BOSS，团队人数限制也不同。大维是一个迷信的人，他总认为奇数比较吉利，偶数不吉利。

题目描述

现在除他以外的在线人数是 N，他希望在这 N 个人中挑选 K 个人和他组成团队去挑战一个 BOSS。而他认为如果可选组队方案总数是奇数的话就能挑战成功，若可选组队方案总数是偶数的话就会挑战失败。当然他认为如果选的是 (1,2,3)、(2,1,3)、(3,2,1) 等都属于同一个方案。但大维的数学学得不好，所以请你帮助他计算一下，他能否挑战成功。若能成功则输出 1，若不能成功则输出 0。

提示
大维一拍脑门突然想到 n 个人里面挑选 k 个人，方案数为 $$C(n,k)$$

但是岐岐大喊一声，跳了出来，又一拍大维的脑门说道：“动动你的脑子，你看看数据规模，你这 $$C(n,k)$$ 算得出来么！”

输入格式

第一行包含一个整数 T，表示测试用例的组数。
接下来 T 行，每行包含两个非负整数 N 和 K（保证 $0\le K\le N$）。

输出格式

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

样例

2
1 1
2 1

1
0

样例解释

样例1：N=1, K=1，方案数 $C(1,1)=1$，为奇数，输出 1。
样例2：N=2, K=1，方案数 $C(2,1)=2$，为偶数，输出 0。

数据范围

• 对于 30% 的数据，$1 \le N \le 10$，$T \le 10^4$
• 对于 50% 的数据，$1 \le N \le 10^3$，$T \le 10^5$
• 对于 100% 的数据，$1 \le N \le 10^9$，$T \le 10^5$