


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}. TaskWrite a program which:
InputIn 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. OutputOne 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. 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 