#P1869. 愚蠢的组合数

愚蠢的组合数

题目描述

最近老师教了狗狗怎么算组合数,狗狗又想到了一个问题。。。

狗狗定义 C(N,K)C(N,K) 表示从 NN 个元素中不重复地选取 KK 个元素的方案数。

狗狗想知道的是 C(N,K)C(N,K) 的奇偶性。

当然,这个整天都老是用竖式算 123456789×987654321=?123456789 \times 987654321=? 的人不会让你那么让自己那么轻松,它说:“ NNKK 都可能相当大”。

但是狗狗也犯难了,所以它就找到了你,想请你帮他解决这个问题。

输入格式

第一行一个正整数 tt,表示数据的组数。

22 至第 2+t12+t-1 行,每行有两个非负整数 NNKK,描述每组数据。数据保证 knk\le n

输出格式

每一组输入,如果 C(N,K)C(N,K) 是奇数则输出 11,否则输出 00

3
1 1
1 0
2 1
1
1
0

提示

数据范围及约定

对于 100%100\% 的数据,1n1051\le n\le 10^51t1051\le t\le 10^5