G. GCD Spanning Tree
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Consider a weighted undirected graph on $$$n$$$ vertices, numbered $$$1$$$ through $$$n$$$. For all $$$1 \le i \lt j \le n$$$, there is an edge between vertices $$$i$$$ and $$$j$$$ with a weight $$$\gcd(i,j)$$$.

You are given an integer $$$k$$$. Construct a spanning tree on the graph with total weight exactly equal to $$$k$$$, or report that it doesn't exist.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 5\cdot 10^5$$$).

The only line of each test contains $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le 10^{12}$$$).

It is guaranteed the sum of $$$n$$$ across all tests does not exceed $$$10^6$$$.

Output

For each test, if the answer does not exist, output -1.

Otherwise output $$$n-1$$$ lines, containing two integers each, describing the edges in your spanning tree.

If there are multiple answers, you can output any.

Example
Input
5
5 5
2 1
2 2
10 1000000000000
6 7
Output
1 2
2 4
2 3
4 5

1 2

-1

-1

1 2
2 4
2 6
1 5
5 3
Note

In the first test, all edges in our outputted spanning tree have weight $$$1$$$ (since $$$\gcd(1,2)=\gcd(2,3)=\gcd(4,5)=1$$$), except for the edge $$$(2,4)$$$, with a weight $$$\gcd(2,4)=2$$$. So the total weight of our spanning tree is $$$1+2+1+1=5$$$, as desired.

In the second test, there is only a single possible spanning tree, with a weight $$$\gcd(1,2)=1$$$. $$$k=1$$$, so we output it.

In the third and fourth tests, we can show that there are no possible solutions.