삼항식

삼항식 $(x^2 + x + 1)^n$ 을 생각하자. 이 식을 전개했을 때 나타나는 계수 $c_i$ 를 구하려고 한다.

$c_0 + c_1 x + c_2 x^2 + \dots + c_{2n} x^{2n}$

예를 들어 $(x^2 + x + 1)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6$ 이다.

다음을 수행하는 프로그램을 작성하라.

• 두 수 $n$ 과 $i$ 로 이루어진 여러 개의 데이터 집합을 입력받는다.
• 각 데이터 집합에 대해, $(x^2 + x + 1)^n$ 의 전개에서 $x^i$ 의 계수인 $c_i$ 를 $3$ 으로 나눈 나머지 $c_i \bmod 3$ 을 계산한다.
• 계산한 값을 각각 표준 출력에 쓴다.

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $k$ 가 주어진다 ($1 \le k \le 10000$).

이어서 $k$ 개의 데이터 집합이 한 줄에 하나씩 주어진다. 각 데이터 집합은 공백 하나로 구분된 음이 아닌 두 정수 $n$ 과 $i$ 로 이루어진다 ($0 \le n \le 10^{15}$, $0 \le i \le 2n$).

$k$ 개의 줄을 출력한다. $j$ 번째 줄에는 $j$ 번째 데이터 집합에 대한 $c_i \bmod 3$ 값을 나타내는, 음이 아닌 정수 하나를 출력한다.