HZNUOJ

【C系列7.13】她的思考

Tags:   神奇的位运算
Time Limit:  1 s      Memory Limit:   32 MB
Submission:1776     AC:415     Score:77.43

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
2 1 1 1 2
output
1 0

Author

WANG, Xiaoan