题意：
求(S(n,m)\% 2)的值，(n,mleq 10^9)，其中(S(n,m))是指第二类斯特林数。
思路：
因为只需要关注奇偶性，所以递推式可以写为：
- 若(m)为偶数，(S(n,m)=S(n-1,m-1));
- 若(m)为奇数，(S(n,m)=S(n-1,m-1)+S(n-1,m))。
观察第二个式子，和组合数的递推公式一模一样。所以我们可以联想到组合数。
将上述递推式子前面几项的值写出来，会发现偶数列错了前面奇数列一列，若只看奇数列，则为杨辉三角的形式。
那么将(S(n,m))写成组合数的形式就为：
[S(n,m)=C(n-lfloorfrac{m}{2}
floor-1,lceilfrac{m}{2}
ceil-1)
]
具体怎么得出来的在纸上画一画即可。
接下来就关系(C(n,m))的奇偶性，然后有个结论：
- 若(n&m=m)，那么(C(n,m))为奇数；否则为偶数。
然后判断一下就行。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2019/12/10 21:33:03
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1000 + 5;
int n, m;
void run(){
cin >> n >> m;
if((m & 1) == 0) {
--n, --m;
}
n = n - m / 2;
m = (m + 1) / 2;
--n, --m;
if((n & m) == m) cout << 1 << '
';
else cout << 0 << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}