图的代价

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一个包含 $n$ 个点的初始空无向图，点编号为 $1$ 到 $n$。你需要添加恰好 $m$ 条边，且不能出现自环或重边。

连接点 $u,v$ 的边权必须等于 $\gcd(u,v)$。你可以重复执行下列操作任意次：

• 选择一个整数 $k\ge1$；
• 添加恰好 $k$ 条权值为 $k+1$ 的边，本次操作的总代价为 $k+1$。

只有当前仍存在至少 $k$ 条尚未加入、权值为 $k+1$ 的合法边时，才能执行这次操作。求添加恰好 $m$ 条边的最小总代价；若无法做到，输出 $-1$。最终图不要求连通。

输入格式

第一行包含整数 $t$，表示测试组数。

随后每组输入一行两个整数 $n,m$。

输出格式

对每组数据输出一行整数，表示最小总代价；若无法构造，输出 $-1$。

样例输入 1

4
4 1
6 10
9 4
10 11

样例输出 1

2
-1
7
21

数据范围

对所有数据，$1\le t\le10^4$，$2\le n\le10^6$，$1\le m\le n(n-1)/2$，并保证所有测试组的 $\sum n\le10^6$。