Mamy tablicę mieszającą z $m$ slotami, ponumerowanymi od $0$ do $m - 1$. Początkowo sloty są puste.

Mamy $n$ elementów, ponumerowanych od $0$ do $n - 1$, które należy wstawić do tablicy mieszającej w tej kolejności.

Funkcja mieszająca to $h(i) = i^2 \pmod m$, więc element o numerze $i$ zostanie wstawiony do slotu o numerze $(i^2 \pmod m)$.

Ze względu na nietypową implementację, wstawienie elementu do slotu kosztuje $T$, gdzie $T$ jest liczbą elementów, które ten slot już zawiera. Oblicz całkowity koszt wstawienia wszystkich $n$ elementów do tablicy.

Wejście

Pierwsza linia zawiera liczbę całkowitą $t$, oznaczającą liczbę przypadków testowych ($1 \le t \le 5$).

Każdy przypadek testowy jest podany w pojedynczej linii zawierającej dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczej linii wynik.

Przykład

Wejście 1

3
5 4
1234 5678
5 4

Wyjście 1

4
229
4

Uwagi

W pierwszym przypadku testowym elementy $0, 1, 2, 3, 4$ są wstawiane odpowiednio do slotów $0, 1, 0, 1, 0$, co generuje koszty $0 + 0 + 1 + 1 + 2 = 4$.