Description

Recently the teacher taught Doggy how to compute combinations, and Doggy came up with another problem...

Doggy defines $C(N,K)$ as the number of ways to choose $K$ elements from $N$ elements without repetition.

Doggy wants to know the parity of $C(N,K)$.

Of course, the person who is always using long multiplication to compute $123456789 \times 987654321=?$ all day won’t let you off easy. They say: “$N$ and $K$ can be quite large.”

But Doggy is also stumped, so it comes to you for help to solve this problem.

Input Format

The first line contains a positive integer $t$, the number of test cases.

Lines $2$ through $2+t-1$ each contain two non-negative integers $N$ and $K$, describing each test case. The input guarantees $k\le n$.

Output Format

For each test case, output $1$ if $C(N,K)$ is odd; otherwise output $0$.

3
1 1
1 0
2 1

1
1
0

Hint

Constraints

For $100\%$ of the testdata, $1\le n\le 10^5$, $1\le t\le 10^5$.

Translated by ChatGPT 5