Consider a trinomial (x2 + x + 1)n. We are interested in the coefficients ci of the expansion of this trinomial:
c0 + c1x + c2x2 + ... + c2n x2n
For example, (x2 + x + 1)3 = 1 + 3x + 6x2 + 7x3 + 6x4 + 3x5 + x6.
TaskWrite a program which:
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 non-negative 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 j-th line ought to contain one non-negative integer being ci modulo 3 for the numbers from the j-th set.
ExampleFor the following input data:
5 2 0 7 4 4 5 5 3 8 15the correct answer is:
1 2 1 0 2
Print friendly version