The Stirling number of the second kind S(n,m) represents 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}∪{4},{1,2,4}∪{3},{1,3,4}∪{2},{2,3,4}∪{1}, {1,2}∪{3,4},{1,3}∪{2,4},{1,4}∪{2,3}. We can compute S(n,m) using the recurrence, S(n,m)=mS(n−1,m)+S(n−1,m−1), forintegers1<m<n. but your task is slightly different: given integers n and m, compute the parity of S(n,m), i.e. S(n,m) mod 2. Example S(4,2) mod 2 = 1. Write a program that reads two positive integers n and m, computes S(n, m) mod 2, and writes the result. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input consists two integers n and m separated by a space, with 1 ≤ m ≤ n ≤ 1000000000. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output should be the integer S(n, m) mod 2. Sample Input 1 42 Sample Output 1