튜링의 도전

크누스가 튜링의 회고록을 읽다가 튜링이 후계자에게 남긴 흥미로운 문제를 발견했다. 크누스는 최고의 제자인 당신에게 이 문제를 푸는 프로그램을 작성하라고 맡겼지만, 성과는 자신의 것으로 하려고 한다. 크누스와 논문을 공저하는 것이 컴퓨터 과학자에게는 에르되시와 논문을 공저하는 것이 수학자에게 갖는 의미와 같으므로, 당신은 이 부탁을 받아들였다. 크누스를 도와 튜링의 문제를 풀어라.

양의 정수 $X$와 $N$이 주어졌을 때, 집합 $T$를 다음과 같이 정의한다. $T = \left\{ T\_i | 1 \le i \le N + 1\right\}$이고, $T\_i = \binom{N}{i-1}X^{i-1}$이다.

목표는 $S \subseteq \{i|1 \le i \le N + 1\}$이고 $\prod\_{i\in S}{T\_i} \equiv 2 \pmod{4}$를 만족하는 집합 $S$를 고르되, 원소의 합이 최대가 되도록 하는 것이다. 다시 말해, $(1 + X)^N$의 이항 전개에서 항들을 골라 그 곱을 4로 나눈 나머지가 2가 되게 하고, 고른 항들의 번호 합을 최대로 만드는 것이다.

그 최대 합을 구하라.

첫 줄에 질의의 개수를 나타내는 양의 정수 $q$ ($1 \le q \le 500$)가 주어진다. 이어지는 $q$개의 줄에는 각각 공백으로 구분된 두 정수 $X$와 $N$ ($1 \le X < 2^{31}$, $1 \le N < 2^{31}$)이 주어진다.

각 질의마다 최대 합을 한 줄에 출력한다. 그러한 부분집합이 없으면 $0$을 출력한다.