X Olympiad in Informatics 2002/2003

Problem: Trinomial

Author: Krzysztof Sikora

Consider a trinomial (x^{2} + x + 1)^{n}. We are interested in the coefficients c_{i} of the expansion of this trinomial:
c_{0} + c_{1}x + c_{2}x^{2} + ... + c_{2n} x^{2n}
For example, (x^{2} + x + 1)^{3} = 1 + 3x + 6x^{2} + 7x^{3} + 6x^{4} + 3x^{5} + x^{6}.
In the first line of the standard input there is one integer k denoting the number of the data sets, 1 <= k <= 10000. It is followed by k sets of data, one per line. Each set consists of two nonnegative integers n and i separated by a single space, 0 <= n <= 1000000000000000, 0 <= i <= 2n.
One should write k lines to the standard output. The jth line ought to contain one nonnegative integer being c_{i} modulo 3 for the numbers from the jth set.
5 2 0 7 4 4 5 5 3 8 15the correct answer is:
1 2 1 0 2