Il existe une table de hachage avec $m$ emplacements, numérotés de $0$ à $m - 1$. Initialement, les emplacements sont vides.

Il y a $n$ éléments, numérotés de $0$ à $n - 1$, qui doivent être insérés dans la table de hachage dans cet ordre.

La fonction de hachage est $h(i) = i^2 \pmod m$, donc l'élément numéro $i$ sera inséré dans l'emplacement numéro $(i^2 \pmod m)$.

En raison de cette implémentation particulière, l'insertion d'un élément dans un emplacement coûte $T$, où $T$ est le nombre d'éléments que cet emplacement contient déjà. Veuillez calculer le coût total de l'insertion de tous ces $n$ éléments dans la table.

Entrée

La première ligne contient un entier $t$, indiquant le nombre de cas de test ($1 \le t \le 5$).

Chaque cas de test est donné sur une seule ligne avec deux entiers, $n$ et $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

Sortie

Pour chaque cas de test, affichez une seule ligne contenant la réponse.

Exemples

Entrée 1

3
5 4
1234 5678
5 4

Sortie 1

4
229
4

Remarque

Dans le premier cas de test, les éléments $0, 1, 2, 3, 4$ sont insérés respectivement dans les emplacements $0, 1, 0, 1, 0$, entraînant des coûts de $0 + 0 + 1 + 1 + 2 = 4$.