Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. SGPA Calculation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob is a student enrolled in a university program with $$$n$$$ single credit courses this semester.

Each course has a course maximum of $$$2047$$$ and has a cutoff for grades, where a grade $$$10$$$ requires a minimum of $$$1024$$$ marks, $$$9$$$ requires $$$512$$$ marks, and so on. Formally, one must score greater than or equal to $$$2^i$$$ for grade $$$i$$$.

Bob, unfortunately, forgot the marks he scored in each course. All he remembers is the XOR of all the marks he got. Now, Bob wants to maximise his Semester Grade Point Average (SGPA), but he needs your help to calculate it. If Bob's marks in the courses are $$$a_1, \dots, a_n$$$, then their SGPA is $$$\frac1n \sum_{i = 1}^n a_i$$$.

Given the XOR of all the marks he got in his courses your task is to write a program to find the maximium SGPA Bob can achieve this semester.

Here XOR denotes the bitwise XOR operation.

Input

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

The first line of each test case contains two integers $$$n$$$ ($$$2 \le n \le 10^3$$$) and $$$x$$$ ($$$0 \le x \le 2047$$$), representing the number of courses Bob is enrolled in, and the XOR of Bob's marks in the $$$n$$$ courses, respectively.

Output

Output a single integer which represents $$$n$$$ multiplied by the maximum possible SGPA achievable by Bob.

Example
Input
3
2 0
2 1024
3 45
Output
20
19
29
Note

Here's an explanation of the samples,

  1. we can achieve $$$20$$$ by getting marks $$$[1024, 1024]$$$,
  2. we can achieve $$$19$$$ by getting marks $$$[837, 1861]$$$,
  3. we can achieve $$$29$$$ by getting marks $$$[1046, 834, 1913]$$$.
It can be proved that we can't do better.