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

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",((n-m)&((m-1)/2))==0);
/*long s[n+1][m+1];
memset(s,0,sizeof(s[0][0])*(n+1)*(m+1));
s[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=j*s[i-1][j]+s[i-1][j-1];
}
}
cout<<"  ";
for(int j=0;j<=m;j++){
cout<<j<<" ";
}
cout<<endl;
for(int i=0;i<=n;i++){
cout<<i<<" ";
for(int j=0;j<=m;j++){
cout<<s[i][j]%2<<" ";
}
cout<<endl;
}*/
}
return 0;
}``````
Copy The Code &

Input

cmd
1
4 2

Output

cmd
1