$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$)。

各テストケースは、2つの整数 $n$ と $m$ を含む1行で与えられます ($1 \le n \le 10^9, 2 \le m \le 10^9$)。

出力

各テストケースについて、答えを1行で出力してください。

入出力例

入力 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$ となります。