Codeforces Round 949 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

math

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Turtle and an Infinite Sequence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere is a sequence $$$a_0, a_1, a_2, \ldots$$$ of infinite length. Initially $$$a_i = i$$$ for every non-negative integer $$$i$$$.

After every second, each element of the sequence will simultaneously change. $$$a_i$$$ will change to $$$a_{i - 1} \mid a_i \mid a_{i + 1}$$$ for every positive integer $$$i$$$. $$$a_0$$$ will change to $$$a_0 \mid a_1$$$. Here, $$$|$$$ denotes bitwise OR.

Turtle is asked to find the value of $$$a_n$$$ after $$$m$$$ seconds. In particular, if $$$m = 0$$$, then he needs to find the initial value of $$$a_n$$$. He is tired of calculating so many values, so please help him!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$0 \le n, m \le 10^9$$$).

Output

For each test case, output a single integer — the value of $$$a_n$$$ after $$$m$$$ seconds.

Example

Input

90 00 10 21 05 210 120 31145 1419198 10

Output

0 1 3 1 7 11 23 1279 19455

Note

After $$$1$$$ second, $$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ will become $$$[1, 3, 3, 7, 7, 7]$$$.

After $$$2$$$ seconds, $$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ will become $$$[3, 3, 7, 7, 7, 7]$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/17/2024 14:11:25 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|