E. Стоимость графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан первоначально пустой неориентированный граф из $$$n$$$ вершин, пронумерованных от $$$1$$$ по $$$n$$$ (т. е. $$$n$$$ вершин и $$$0$$$ ребер). Вы хотите добавить в него $$$m$$$ ребер так, чтобы граф не содержал петель и кратных ребер.

Если будет добавлено ребро, соединяющее две вершины $$$u$$$ и $$$v$$$, его вес должен быть равен наибольшему общему делителю $$$u$$$ и $$$v$$$, т. е. $$$\gcd(u, v)$$$.

Для того чтобы добавлять ребра в граф, вы можете повторять следующую операцию произвольное количество раз (возможно, ни разу):

  • выбираете целое число $$$k \ge 1$$$;
  • добавляете ровно $$$k$$$ ребер в граф, каждое веса $$$k + 1$$$. Добавление этих $$$k$$$ ребер суммарно стоит $$$k + 1$$$.
Заметим, что вы не можете создавать петли или кратные ребра. А потому, если вы не можете добавить $$$k$$$ ребер веса $$$k + 1$$$, вы не можете выбрать такое $$$k$$$.

Например, если вы можете добавить еще $$$5$$$ ребер веса $$$6$$$, вы можете их добавить в граф, и добавление будет стоить $$$6$$$ за всю группу из $$$5$$$ ребер. Однако если вы можете добавить только $$$4$$$ ребра веса $$$6$$$ в граф, вы не можете выполнить данную операцию для $$$k = 5$$$.

Для заданных $$$n$$$ и $$$m$$$, посчитайте минимальную суммарную стоимость создания графа из $$$n$$$ вершин и ровно $$$m$$$ ребер, используя описанную выше операцию. Если построить такой граф нельзя, выведите $$$-1$$$.

Заметим, что результирующий граф может состоять из нескольких компонент связности.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой и единственной строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^6$$$; $$$1 \leq m \leq \frac{n(n-1)}{2}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите наименьшую стоимость построения графа или $$$-1$$$, если такой граф построить нельзя.

Пример
Входные данные
4
4 1
6 10
9 4
10 11
Выходные данные
2
-1
7
21
Примечание

В первом наборе входных данных, мы можем добавить одно ребро между вершинами $$$2$$$ и $$$4$$$ с $$$\gcd = 2$$$. Это единственный способ добавить $$$1$$$ ребро, и он будет стоить $$$2$$$.

Во втором наборе, невозможно добавить $$$10$$$ ребер, а потому ответ $$$-1$$$.

В третьем наборе, мы можем добавить следующие ребра:

  • $$$k = 1$$$: ребро веса $$$2$$$ между вершинами $$$2$$$ и $$$4$$$ ($$$\gcd(2, 4) = 2$$$). Стоимость: $$$2$$$;
  • $$$k = 1$$$: ребро веса $$$2$$$ между вершинами $$$4$$$ и $$$6$$$ ($$$\gcd(4, 6) = 2$$$). Стоимость: $$$2$$$;
  • $$$k = 2$$$: ребра веса $$$3$$$: $$$(3, 6)$$$ и $$$(3, 9)$$$ ($$$\gcd(3, 6) = \gcd(3, 9) = 3$$$). Стоимость: $$$3$$$.
В результате мы добавили $$$1 + 1 + 2 = 4$$$ ребра с общей стоимостью $$$2 + 2 + 3 = 7$$$, что является оптимальным ответом.