Polish version    English version  

 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
X Olympiad in Informatics 2002/2003

Problem: Trinomial
Author: Krzysztof Sikora

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.


Write a program which:
  • reads from the standard input sets of data that comprise numbers n and i,
  • for each set of data computes ci modulo 3, where ci is the coefficient of xi in the expansion of the trinomial (x2 + x + 1)n,
  • for each set of data writes the computed number to the standard output.


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.


For the following input data:
2 0
7 4
4 5
5 3
8 15
the correct answer is:

Print friendly version