Cookie Breeding Machine

AtCoder

IDkupc2016_c

Time1000ms

Memory256MB

Difficulty—

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](https://en.wikipedia.org/wiki/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. [samples]

Samples

Input #1

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.

API Response (JSON)

{
  "problem": {
    "name": "Cookie Breeding Machine",
    "description": {
      "content": "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 equa",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "kupc2016_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A professor invented Cookie Breeding Machine for his students who like cookies very much.\nWhen one cookie with the taste of $x$ is put into the machine and a non-negative integer $y$ less than or equa...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments