Description:
You are given an initially empty undirected graph with $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$ (i. e. $$$n$$$ nodes and $$$0$$$ edges). You want to add $$$m$$$ edges to the graph, so the graph won't contain any self-loop or multiple edges.
If an edge connecting two nodes $$$u$$$ and $$$v$$$ is added, its weight must be equal to the greatest common divisor of $$$u$$$ and $$$v$$$, i. e. $$$\gcd(u, v)$$$.
In order to add edges to the graph, you can repeat the following process any number of times (possibly zero):
- choose an integer $$$k \ge 1$$$;
- add exactly $$$k$$$ edges to the graph, each having a weight equal to $$$k + 1$$$. Adding these $$$k$$$ edges costs $$$k + 1$$$ in total.
For example, if you can add $$$5$$$ more edges to the graph of weight $$$6$$$, you may add them, and it will cost $$$6$$$ for the whole pack of $$$5$$$ edges. But if you can only add $$$4$$$ edges of weight $$$6$$$ to the graph, you can't perform this operation for $$$k = 5$$$.
Given two integers $$$n$$$ and $$$m$$$, find the minimum total cost to form a graph of $$$n$$$ vertices and exactly $$$m$$$ edges using the operation above. If such a graph can't be constructed, output $$$-1$$$.
Note that the final graph may consist of several connected components.
Input Format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^6$$$; $$$1 \leq m \leq \frac{n(n-1)}{2}$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
Output Format:
For each test case, print the minimum cost to build the graph, or $$$-1$$$ if you can't build such a graph.
Note:
In the first test case, we can add an edge between the vertices $$$2$$$ and $$$4$$$ with $$$\gcd = 2$$$. This is the only possible way to add $$$1$$$ edge that will cost $$$2$$$.
In the second test case, there is no way to add $$$10$$$ edges, so the answer is $$$-1$$$.
In the third test case, we can add the following edges:
- $$$k = 1$$$: edge of weight $$$2$$$ between vertices $$$2$$$ and $$$4$$$ ($$$\gcd(2, 4) = 2$$$). Cost: $$$2$$$;
- $$$k = 1$$$: edge of weight $$$2$$$ between vertices $$$4$$$ and $$$6$$$ ($$$\gcd(4, 6) = 2$$$). Cost: $$$2$$$;
- $$$k = 2$$$: edges of weight $$$3$$$: $$$(3, 6)$$$ and $$$(3, 9)$$$ ($$$\gcd(3, 6) = \gcd(3, 9) = 3$$$). Cost: $$$3$$$.