A. And Matching
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of $$$n$$$ ($$$n$$$ is always a power of $$$2$$$) elements containing all integers $$$0, 1, 2, \ldots, n-1$$$ exactly once.

Find $$$\frac{n}{2}$$$ pairs of elements such that:

  • Each element in the set is in exactly one pair.
  • The sum over all pairs of the bitwise AND of its elements must be exactly equal to $$$k$$$. Formally, if $$$a_i$$$ and $$$b_i$$$ are the elements of the $$$i$$$-th pair, then the following must hold: $$$$$$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation.

If there are many solutions, print any of them, if there is no solution, print $$$-1$$$ instead.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 400$$$) — the number of test cases. Description of the test cases follows.

Each test case consists of a single line with two integers $$$n$$$ and $$$k$$$ ($$$4 \leq n \leq 2^{16}$$$, $$$n$$$ is a power of $$$2$$$, $$$0 \leq k \leq n-1$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$2^{16}$$$. All test cases in each individual input will be pairwise different.

Output

For each test case, if there is no solution, print a single line with the integer $$$-1$$$.

Otherwise, print $$$\frac{n}{2}$$$ lines, the $$$i$$$-th of them must contain $$$a_i$$$ and $$$b_i$$$, the elements in the $$$i$$$-th pair.

If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.

Example
Input
4
4 0
4 1
4 2
4 3
Output
0 3
1 2
0 2
1 3
0 1
2 3
-1
Note

In the first test, $$$(0\&3)+(1\&2) = 0$$$.

In the second test, $$$(0\&2)+(1\&3) = 1$$$.

In the third test, $$$(0\&1)+(2\&3) = 2$$$.

In the fourth test, there is no solution.