[Hidden]

#### Description

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 Problem:

The challenge is as follows:

Given positive integer values for X and N, define the set T as follows: The goal of the challenge is to pick a set S of maximal sum with , such that

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

The product:

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 (mod 4).

#### Input

The first input line contains a positive integer,, indicating the number of queries. Each of the next q lines will contain a pair of space-separated integers, where the first integer is , and the second integer is, for that query.

#### Output

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.

#### Samples

Input Copy
3
3 5
1 4
4 6

Output
18
9
0


#### Source

UCF Local Programming Contest 2015
##### Problem Information

 Time Limit: 5000MS (C/C++,Others×2) Memory Limit: 128MB (C/C++,Others×2) Special Judge: No AC/Submit: 1 / 1 Tags:
##### Contests involved

 1030. UCF 2015