Existe una tabla hash con $m$ ranuras, numeradas de $0$ a $m - 1$. Inicialmente, las ranuras están vacías.

Hay $n$ elementos, numerados de $0$ a $n - 1$, que deben insertarse en la tabla hash en este orden.

La función hash es $h(i) = i^2 \pmod m$, por lo que el elemento número $i$ se insertará en la ranura numerada $(i^2 \pmod m)$.

Debido a la extraña implementación, insertar un elemento en una ranura tiene un costo de $T$, donde $T$ es el número de elementos que esta ranura ya contiene. Por favor, calcule el costo total de insertar todos estos $n$ elementos en la tabla.

Entrada

La primera línea contiene un entero $t$, que denota el número de casos de prueba ($1 \le t \le 5$).

Cada caso de prueba se proporciona en una sola línea con dos enteros, $n$ y $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

Salida

Para cada caso de prueba, imprima una sola línea que contenga la respuesta.

Ejemplos

Entrada 1

3
5 4
1234 5678
5 4

Salida 1

4
229
4

Nota

En el primer caso de prueba, los elementos $0, 1, 2, 3, 4$ se insertan en las ranuras $0, 1, 0, 1, 0$ respectivamente, incurriendo en costos de $0 + 0 + 1 + 1 + 2 = 4$.