Существует хеш-таблица с $m$ ячейками, пронумерованными от $0$ до $m - 1$. Изначально все ячейки пусты.

Имеется $n$ элементов, пронумерованных от $0$ до $n - 1$, которые необходимо вставить в хеш-таблицу в данном порядке.

Хеш-функция имеет вид $h(i) = i^2 \pmod m$, поэтому элемент с номером $i$ будет вставлен в ячейку с номером $(i^2 \pmod m)$.

Из-за особенностей реализации, вставка элемента в ячейку стоит $T$, где $T$ — количество элементов, которые уже содержатся в этой ячейке. Вычислите общую стоимость вставки всех $n$ элементов в таблицу.

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

Первая строка содержит целое число $t$, обозначающее количество тестов ($1 \le t \le 5$).

Каждый тест задается одной строкой, содержащей два целых числа $n$ и $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

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

Для каждого теста выведите одну строку, содержащую ответ.

Примеры

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

3
5 4
1234 5678
5 4

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

4
229
4

Примечание

В первом тесте элементы $0, 1, 2, 3, 4$ вставляются в ячейки $0, 1, 0, 1, 0$ соответственно, что приводит к затратам $0 + 0 + 1 + 1 + 2 = 4$.