$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$). 각 테스트 케이스는 한 줄에 두 정수 $n$과 $m$이 주어집니다 ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

출력

각 테스트 케이스마다 정답을 한 줄에 출력하십시오.

예제

입력 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$가 발생합니다.