AT_kupc2016_c クッキー☆増殖装置

[problemUrl]: https://atcoder.jp/contests/kupc2016/tasks/kupc2016_c クッキー好きの学生たちのために、ある教授がクッキー増殖装置を発明した。 この装置に美味しさ $ x $ のクッキー1枚を投入し、$ 0 $ 以上 $ 127 $ 以下の整数 $ y $ を入力すると、 投入したクッキーを消費して、美味しさ $ y $ と美味しさ ($ x $ XOR $ y $) の2枚のクッキーが生成される。 ここで、XORはビットごとの[排他的論理和](https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C)を表す。 最初、クッキーは1枚だけあり、美味しさは $ D $ である。 以下の操作を $ N-1 $ 回繰り返して生成された、ちょうど $ N $ 枚のクッキーの美味しさの合計の最大値を出力せよ。 1. 今あるクッキーのうちいずれか1枚を選んで装置に投入する。 2. $ 0 $ 以上 $ 127 $ 以下の整数から自由に1つ選んで装置に入力する。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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) $ ### Sample Explanation 1 $ 1 $ つ目のテストケースでは、以下の手順で装置を使用すると、最終的に、美味しさ $ 61 $, $ 95 $, $ 99 $ の $ 3 $ 枚のクッキーが生成され、美味しさの合計が最大であるため、$ 255 $ と出力する。 1. 美味しさ $ 1 $ のクッキーを投入して消費し、装置に $ 60 $ を入力すると、美味しさ $ 60 $ のクッキーと美味しさ $ 61 $ のクッキーが生成される。 2. 美味しさ $ 60 $ のクッキーを投入して消費し、装置に $ 99 $ を入力すると、美味しさ $ 99 $ のクッキーと美味しさ $ 95 $ のクッキーが生成される。 また、 $ 3 $ つ目のテストケースのように、装置を使用しないこともある。