Harshith attained enlightenment in Competitive Programming by training under a Divine Tree. A divine tree is a rooted tree$^{\text{∗}}$ with $n$ nodes, labelled from $1$ to $n$. The divineness of a node $v$, denoted $d(v)$, is defined as the smallest node label on the unique simple path from the root to node $v$.

Aryan, being a hungry Competitive Programmer, asked Harshith to pass on the knowledge. Harshith agreed on the condition that Aryan would be given two positive integers $n$ and $m$, and he had to construct a divine tree with $n$ nodes such that the total divineness of the tree is $m$, i.e., $\displaystyle\sum\limits_{i=1}^n d(i)=m$. If no such tree exists, Aryan must report that it is impossible.

Desperate for knowledge, Aryan turned to you for help in completing this task. As a good friend of his, help him solve the task.

$^{\text{∗}}$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

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$ and $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^{12}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer $k$ in one line — the root of the tree.

Then $n-1$ lines follow, each containing a description of an edge of the tree — a pair of positive integers $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$), denoting the $i$-th edge connects vertices $u_i$ and $v_i$.

The edges and vertices of the edges can be printed in any order. If there are multiple solutions, print any of them.

If there is no solution, print "-1" instead.

Note

In the first test case, there is a single node with a value of $1$, so getting a sum of $2$ is impossible.

In the second test case, getting a sum of $6$ is possible with the given tree rooted at $3$.