## 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.

### Task

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
```

hide comments
 < Previous 1 2 Next > Anubhav Balodhi : 2014-08-13 17:02:56 Sierpinski Gasket does it all ^_^ ankitsablok89: 2014-08-08 23:22:21 Learnt so much through this problem :)for further reading go to these links - http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind and http://en.wikipedia.org/wiki/Sierpinski_triangle j1k7_7(JaskamalKainth): 2014-07-12 11:00:31 O(1) utkarsh agarwal: 2013-12-16 21:07:34 gives runtime error...whie code runs well on ideone. Parshant garg: 2013-08-04 04:58:02 what is answer for 0 1 my program give 1 and accepted Mitch Schwartz: 2013-04-25 14:14:18 I don't know why so many people are leaving comments about how the solution can be found by searching the internet; I still remember the satisfaction I got from doing it on paper. [Lakshman]: 2013-04-25 14:14:18 Last edit: 2013-03-30 09:00:04 sachin kumar: 2012-10-06 10:39:51 it is showing SIGSEGV but it is working in ideone.com saibharath: 2011-01-24 16:59:03 plz provide some more test cases Last edit: 2011-01-24 16:59:21

 Added by: adrian Date: 2004-07-02 Time limit: 3s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: ACM Central European Programming Contest, Warsaw 2001