시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

There is a hash table with $m$ slots, numbered from $0$ to $m-1$. Initially the slots are empty.

There are $n$ elements, numbered from $0$ to $n-1$, which should be inserted into the hash table in this order.

The hash function is $h(x)=x^2 \bmod m$, so the element number $i$ will be inserted into the slot numbered $(i^2 \bmod m)$.

Because of the strange implementation, inserting an element into a slot costs $T$, where $T$ is the number of elements this slot already contains. Please compute the total cost of inserting all these $n$ elements into the table.

입력

The first line contains an integer $t$, denoting the number of test cases ($1 \le t \le 5$).

Each test case is given on a single line with two integers, $n$ and $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

출력

For each test case, print a single line containing the answer.

예제 입력 1

3
5 4
1234 5678
5 4

예제 출력 1

4
229
4

힌트

In the first test case, the elements $0,1,2,3,4$ are inserted into slots $0,1,0,1,0$ respectively, incurring costs of $0+0+1+1+2=4$.