   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Binary Stirling Numbers
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2073 Accepted: 844

Description

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

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

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 <= 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(ni, mi) mod 2.

Sample Input

```1
4 2```

Sample Output

`1`

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top