买花

描述

小 L 喜欢花，花店里有 N 种颜色的花各一朵，小 L 打算买 K 种颜色的花，小L 有多种买花的方案。由于 N 和 K 可能很大，所以小 L 想知道她买花方案数的奇偶性。（即N 种颜色的花中不重复地选取 K 种颜色的花的方案数的奇偶性）

输入格式：

第 1 行：一个正整数 Q，表示数据的组数。 第 2~2+Q-1 行：两个非负整数，花颜色的种类 N 和小 L 想买的花的数量K。

输出格式

每一组输入，如果方案数是奇数则输出 1，否则输出 0

输入数据 1

3 1 1 1 0 2 1

输出数据 1

1 1 0

注：

1.用递归和递推可能不行，会爆掉 2.对于 30% 的数据，n<=10^2 Q<=10^4 对于 50% 的数据，n<=10^3 Q<=10^5 对于 100%的数据，n<=10^9 Q<=10^5

3.教练的提示是：其实就是一个 2 2

 一个三角形分解为四个的三角形，中间一个三角形全为 0， 余下三个三角形继续分解。详见程序和下面的附表 这个规律比较严格的描述是这样的，设 N=X a X a-1 X a-2 …X 1（2） ， K=Y b Y b-1 Y b-2 …Y 1（2） （即用二进制表示）C(n,k)为偶的充分必要条件是存在 i 使得 X i <Y i 这样可以通过 100%的点。