J. AND Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$ and $$$k$$$. An array $$$a$$$ is considered good if the following conditions hold:

  • The length of $$$a$$$ is equal to $$$n$$$.
  • $$$a$$$ contains positive integers.
  • The sum of elements of $$$a$$$ is equal to $$$k$$$ (i.e. $$$\sum a_i = k$$$).

The cost of the array $$$a$$$ is equal to the sum of $$$a_i$$$ $$$\&$$$ $$$a_{i - 1}$$$ for all $$$i$$$ such that $$$1 \lt i \le n$$$, where $$$\&$$$ is the bitwise AND$$$^{[9]}$$$ operator.

Your task is to find the minimum cost of a good array.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each line of the following $$$t$$$ lines of the input consists of two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6, n \le k \le 10^9$$$).

Notice that there is no limit on the sum of $$$n$$$ over all the test cases.

Output

Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the minimum cost of a good array in the $$$i$$$-th testcase.

Example
Input
3
1 2
2 3
4 5
Output
0
0
1