愚蠢的组合数

题目描述

最近老师教了狗狗怎么算组合数,狗狗又想到了一个问题。。。 狗狗定义 $C(N,K)$ 表示从 $N$ 个元素中不重复地选取 $K$ 个元素的方案数。 狗狗想知道的是 $C(N,K)$ 的奇偶性。 当然,这个整天都老是用竖式算 $123456789 \times 987654321=?$ 的人不会让你那么让自己那么轻松,它说:“ $N$ 和 $K$ 都可能相当大”。 但是狗狗也犯难了,所以它就找到了你,想请你帮他解决这个问题。

输入输出格式

输入格式


第一行一个正整数 $t$,表示数据的组数。 第 $2$ 至第 $2+t-1$ 行,每行有两个非负整数 $N$ 和 $K$,描述每组数据。数据保证 $k\le n$。

输出格式


每一组输入,如果 $C(N,K)$ 是奇数则输出 $1$,否则输出 $0$。

输入输出样例

输入样例 #1

3
1 1
1 0
2 1

输出样例 #1

1
1
0

说明

### 数据范围及约定 对于 $100\%$ 的数据,$1\le n\le 10^5$,$1\le t\le 10^5$。