有一个哈希表，包含 $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$。