eolymp
bolt
Try our new interface for solving problems
Problems

Binary Stirling Numbers

Binary Stirling Numbers

Time limit 1 second
Memory limit 64 MiB

The Stirling number of the second kindS(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 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) = mS(n - 1, m) + S(n - 1, m - 1), for n, m > 0.

Your task is much "easier". Given integers n and m satisfying 1mn, compute the parity of S(n, m), i.e. S(n, m) mod 2.

Example, S(4, 2) mod 2 = 1.

Write a program which for each data set:

  • reads two positive integers n and m,

  • computes S(n, m) mod 2,

  • writes the result.

Input data

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1d200. The data sets follow.

Line i+1 contains the i-th data set - exactly two integers n_i and m_i separated by a single space, 1m_in_i10^9.

Output data

The output should consist of exactly d lines, one line for each data set. Line i, 1id, should contain 0 or 1, the value of S(n_i, m_i) mod 2.

Examples

Input example #1
1
4 2
Output example #1
1
Source II этап Всеукраинской олимпиады школьников 2012-2013, г. Бердичев