25942번 - Turing’s Challenge 다국어

문제

Knuth was looking through some of Turing's memoirs and found a rather interesting challenge that Turing had left for one of his successors. Naturally, Knuth has slyly decided to ask you, his best student, to write a computer program to solve the challenge, but plans on taking credit for the work. Since you know that co-authoring a paper with Knuth is to computer scientists what co-authoring a paper with Erdos is to mathematicians, you've decided to take the bait. Help Knuth solve Turing's problem!

The challenge is as follows:

Given positive integer values for $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 of the challenge is to pick a set $S$ of maximal sum with $S ⊆ \left\{i|1 ≤ i ≤ N + 1\right\},ドル such that $∏_{i∈S}{T_i} ≡ 2 \pmod{4}$.

In other words, we seek a subset of terms in the binomial expansion of $(1 + X)^N$ such that the product of the terms leaves a remainder of 2ドル$ when divided by 4ドル$ and the sum of the indices of those terms is maximal.

The goal of Turing's challenge is to determine this maximal sum.

As an example, consider $X = 3$ and $N = 5$. The corresponding terms are $T_1 = 1,ドル $T_2 = 15,ドル $T_3 = 90,ドル $T_4 = 270,ドル $T_5 = 405,ドル and $T_6 = 243$.

The product, $T_1T_2T_4T_5T_6 = 1 × 15 × 270 × 405 × 243 = 398580750 ≡ 2 \pmod{4},ドル thus the solution to this specific challenge is 1ドル + 2 +たす 4 +たす 5 +たす 6 =わ 18,ドル since no other product of terms with a higher sum of indices is congruent to 2ドル \pmod{4}$.

입력

The first input line contains a positive integer, $q$ (1ドル ≤ q ≤ 500$), indicating the number of queries. Each of the next $q$ lines will contain a pair of space-separated integers, where the first integer is $X$ (1ドル ≤ X < 2^{31}$), and the second integer is $N$ (1ドル ≤ N < 2^{31}$), for that query.

출력

For each query, output on a line by itself, the desired maximal sum of indices. If no such subset of terms exists, output 0ドル$ instead.

제한

힌트