P5947 [POI 2003] Trinomial
Description
Find the coefficient of the $i$-th term of $(x^2 + x + 1)^n$.
Input Format
The first line contains an integer $k$, the number of test cases.
The next $k$ lines each contain two integers $n, i$.
Output Format
For each test case, output the result of $x_i \bmod 3$.
Explanation/Hint
Constraints: for $100\%$ of the testdata, $1 \le k \le 10000$, $0 \le n \le 10^{15}$, and $0 \le i \le 2 \times n$.
Translated by ChatGPT 5