排列组合C(n k)计算公式

Description

C(n, 0) = C(n, n) = 1 对所有的n>0

C(n, k) = C(n − 1, k − 1) + C(n − 1, k) 对所有 0 < k < n.

求C(n, k)与2的余数。

Input

第一行输入一个整数t，代表有多少个数据。接下来的t行输入两个整数k，n(0 ≤ k ≤ n < 2^31, n > 0)。

Output

C(n, k)与2的余数。

Samples

input Copy

2

1 1

1 2

output Copy

1

0

Show after trying 4 times:

input Copy

5

284 408

262 265

398 955

556 818

108 309

output Copy

0

0

0

0

0

简析：排列组合计算公式C(n, k) = C(n − 1, k − 1) + C(n − 1, k)。