Graph Cost
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.
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$.
For each test case, print the minimum cost to build the graph, or $-1$ if you can't build such a graph.
Input
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
For each test case, print the minimum cost to build the graph, or $-1$ if you can't build such a graph.
4
4 1
6 10
9 4
10 11
2
-1
7
21
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$.