Turing's Challenge

Knuth was reading through some of Turing's memoirs and found an interesting challenge that Turing had left for one of his successors. Knuth asked you, his best student, to write a program that solves it, but he plans to take the credit for the work. Co-authoring a paper with Knuth is to computer scientists what co-authoring a paper with Erdos is to mathematicians, so you accept the task. Help Knuth solve Turing's problem.

Given positive integers $X$ and $N$, define the set $T$ as follows: $T = \left\{ T\_i | 1 \le i \le N + 1\right\}$, where $T\_i = \binom{N}{i-1}X^{i-1}$.

The goal is to pick a set $S$ with $S \subseteq \{i|1 \le i \le N + 1\}$ such that $\prod\_{i\in S}{T\_i} \equiv 2 \pmod{4}$, and the sum of the elements of $S$ is as large as possible. In other words, you choose terms from the binomial expansion of $(1 + X)^N$ so that their product leaves remainder 2 when divided by 4, and the sum of their indices is maximal.

Find that maximal sum.

The first line contains a positive integer $q$ ($1 \le q \le 500$), the number of queries. Each of the next $q$ lines contains two space-separated integers $X$ and $N$ ($1 \le X < 2^{31}$, $1 \le N < 2^{31}$).

For each query, print the maximal sum of indices on its own line. If no such subset exists, print $0$.