P1869 Silly Binomial Coefficient

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.

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

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

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