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 fourelement 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(n1, m) + S(n1, m1), 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 ith data set  exactly two integers n_{i} and m_{i} separated by a single space, 1 < = m_{i} < = n_{i} <= 10^{9}.
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(n_{i}, m_{i}) mod 2.
Example
Sample input: 1 4 2 Sample output: 1
hide comments
Anubhav Balodhi :
20140813 17:02:56
Sierpinski Gasket does it all ^_^ 

ankitsablok89:
20140808 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):
20140712 11:00:31
O(1) 

utkarsh agarwal:
20131216 21:07:34
gives runtime error...whie code runs well on ideone.


Parshant garg:
20130804 04:58:02
what is answer for 0 1 my program give 1 and accepted 

Mitch Schwartz:
20130425 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]:
20130425 14:14:18
Last edit: 20130330 09:00:04 

sachin kumar:
20121006 10:39:51
it is showing SIGSEGV but it is working in ideone.com


saibharath:
20110124 16:59:03
plz provide some more test cases Last edit: 20110124 16:59:21 
Added by:  adrian 
Date:  20040702 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ACM Central European Programming Contest, Warsaw 2001 