C - クッキー☆増殖装置 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

クッキー好きの学生たちのために、ある教授がクッキー増殖装置を発明した。

この装置に美味しさ x のクッキー1枚を投入し、0 以上 127 以下の整数 y を入力すると、 投入したクッキーを消費して、美味しさ y と美味しさ (x XOR y) の2枚のクッキーが生成される。

ここで、XORはビットごとの排他的論理和を表す。

最初、クッキーは1枚だけあり、美味しさは D である。

以下の操作を N-1 回繰り返して生成された、ちょうど N 枚のクッキーの美味しさの合計の最大値を出力せよ。

  1. 今あるクッキーのうちいずれか1枚を選んで装置に投入する。
  2. 0 以上 127 以下の整数から自由に1つ選んで装置に入力する。

制約

  • 1 \leq T \leq 1000
  • 1 \leq N_t \leq 1000 (1 \leq t \leq T)
  • 1 \leq D_t \leq 127 (1 \leq t \leq T)

入力

入力は以下の形式で標準入力から与えられる。

T
N_1 D_1
:
N_T D_T

入力は複数のテストケースからなる。1 行目には、テストケースの個数を表す整数 T が与えられる。
続く T 行にテストケースが1つずつ与えられる。
t ( 1 \leq t \leq T ) 番目のテストケースでは、 半角スペース区切りで最終的なクッキーの枚数を表す整数 N_t と最初のクッキーの美味しさ D_t が与えられる。

出力

最終生成物となる N 枚クッキーの美味しさの合計の最大値を標準出力に1行で出力せよ。

入力例1

3
3 1
4 108
1 10

出力例1

255
400
10

1 つ目のテストケースでは、以下の手順で装置を使用すると、最終的に、美味しさ 61, 95, 99 の 3 枚のクッキーが生成され、美味しさの合計が最大であるため、255 と出力する。

  1. 美味しさ 1 のクッキーを投入して消費し、装置に 60 を入力すると、美味しさ 60 のクッキーと美味しさ 61 のクッキーが生成される。
  2. 美味しさ 60 のクッキーを投入して消費し、装置に 99 を入力すると、美味しさ 99 のクッキーと美味しさ 95 のクッキーが生成される。

また、 3 つ目のテストケースのように、装置を使用しないこともある。

Score : 100 points

Problem Statement

A professor invented Cookie Breeding Machine for his students who like cookies very much.

When one cookie with the taste of x is put into the machine and a non-negative integer y less than or equal to 127 is input on the machine, it consumes the cookie and generates two cookies with the taste of y and (x XOR y).

Here, XOR represents Bitwise Exclusive OR.

At first, there is only one cookie and the taste of it is D .

Find the maximum value of the sum of the taste of the exactly N cookies generated after the following operation is conducted N-1 times.

  1. Put one of the cookies into the machine.
  2. Input a non-negative integer less than or equal to 127 on the machine.

Constraints

  • 1 \leq T \leq 1000
  • 1 \leq N_t \leq 1000 (1 \leq t \leq T)
  • 1 \leq D_t \leq 127 (1 \leq t \leq T)

Input

The input is given from Standard Input in the following format:

T
N_1 D_1
:
N_T D_T

The input consists of multiple test cases. An Integer T that represents the number of test cases is given on line 1.
Each test case is given on the next T lines.
In the t-th test case ( 1 \leq t \leq T ), N_t that represents the number of cookies generated through the operations and D_t that represents the taste of the initial cookie are given separated by space.

Output

For each test case, print the maximum value of the sum of the taste of the N cookies generated through the operations on one line.

Sample Input 1

3
3 1
4 108
1 10

Sample Output 1

255
400
10

On the 1st test case, if the machine is used as follows, three cookies with the taste of 61, 95 and 99 are generated. Since the sum of these values is maximum among all possible ways, the answer is 255.

  1. Put the cookie with the taste of 1 and input an integer 60 on the machine, lose the cookie and get two cookies with the taste of 60 and 61.
  2. Put the cookie with the taste of 60 and input an integer 99 on the machine, lose the cookie and get two cookies with the taste of 99 and 95.

On the 3rd test case, the machine may not be used.

出典

KUPC2016