本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1274. K.Turing’s Challenge


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 S{1iN+1}, such thatiSTi2(mod 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 areT1=1,T2=15,T3=90,T4=270,T5=405,and T6=243.

The product:

T1T2T3T4T5T6=1×15×90×270×243=3985807502(mod 4)

thus the solution to this specific challenge is 1+2+4+5+6=181+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,q(1q500), 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(1X<231), and the second integer isN(1N<231), 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
My history solutions

You didn't submit any solution!
Submit your solution

Login Register