Alternatywne formaty: PostScript | PDF

Rozważmy wielomian (x² + x + 1)ⁿ. Interesują nas współczynniki c_i rozwinięcia tego wielomianu:

c₀ + c₁x + c₂x² + ... + c_2n x²ⁿ

Na przykład, (x² + x + 1)³ = 1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia zestawy danych w których są liczby n oraz i,
• dla każdego zestawu obliczy resztę z dzielenia przez 3 współczynnika c_i stojącego przy xⁱ w rozwinięciu wielomianu (x² + x + 1)ⁿ,
• dla każdego zestawu wypisze na standardowe wyjście obliczoną resztę.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita k określająca liczę zestawów danych, 1 <= k <= 10000. Po niej następuje k zestawów danych, po jednym w wierszu. W każdym zestawie danych zapisane są dwie nieujemne liczby całkowite n oraz i oddzielone pojedynczym odstępem, 0 <= n <= 1000000000000000, 0 <= i <= 2n.

Wyjście

Przykład

Dla danych wejściowych:

5
2 0
7 4
4 5
5 3
8 15

poprawnym wynikiem jest:

1
2
1
0
2