## BINSTIRL - Binary Stirling Numbers

The Stirling number of the second kind S(n, m) stands for the number of ways to partition a set of n things into m nonempty subsets. For example, there are seven ways to split a four-element set into two parts: {1, 2, 3} u {4}, {1, 2, 4} u {3}, {1, 3, 4} u {2}, {2, 3, 4} u {1}, {1, 2} u {3, 4}, {1, 3} u {2, 4}, {1, 4} u {2, 3}.

There is a recurrence which allows you to compute S(n, m) for all m and n.
S(0, 0) = 1,
S(n, 0) = 0, for n > 0,
S(0, m) = 0, for m > 0,
S(n, m) = m*S(n-1, m) + S(n-1, m-1), for n, m > 0.

Your task is much "easier". Given integers n and m satisfying 1 <= m <= n, compute the parity of S(n, m), i.e. S(n, m) mod 2.

For instance, S(4, 2) mod 2 = 1.

Write a program that:

• reads two positive integers n and m,
• computes S(n, m) mod 2,
• writes the result.

### Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 200. The data sets follow.

Line i + 1 contains the i-th data set - exactly two integers ni and mi separated by a single space, 1 < = mi < = ni <= 109.

### Output

The output should consist of exactly d lines, one line for each data set. Line i, 1 <= i < = d, should contain 0 or 1, the value of S(ni, mi) mod 2.

### Example

```Sample input:
1
4 2

Sample output:
1
```

 < Previous 1 2 Next > sacsachin: 2020-05-10 21:31:24 AC ... O(1) :) cake_is_a_lie: 2017-03-03 14:06:11 OK, challenge accepted and completed: AC with O(1), without help from teh internets. For me, visual representation was key. Last edit: 2017-03-03 14:07:12 rahulpadhy: 2016-08-24 04:56:14 How to derive the formula of the parity of the stirling numbers of the second kind that works in O(1) time ? gautam: 2016-04-26 15:07:54 O(1)...;-) Vishesh Middha: 2015-08-15 14:49:57 providing SIGSEGV error why please explain?? (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-07-28 05:54:23 Solve this problem without taking help from net? Challenge accepted ;-) ANIKET: 2015-07-27 07:13:59 Last edit: 2015-07-27 07:15:44 Rajat (1307086): 2014-12-28 23:04:26 Challenge for those who do not know Binary Stirling numbers: "Do this question without taking help from net." sunil gowda: 2014-12-20 09:51:15 how to do in O(1) time .. anyone knows.. parijat bhatt: 2014-10-02 17:12:20 @ j1k7_7(JaskamalKainth) how can it be solved in o(1)