Có một bảng băm với $m$ ô, được đánh số từ $0$ đến $m - 1$. Ban đầu các ô đều trống.

Có $n$ phần tử, được đánh số từ $0$ đến $n - 1$, cần được chèn vào bảng băm theo thứ tự này.

Hàm băm là $h(i) = i^2 \pmod m$, vì vậy phần tử thứ $i$ sẽ được chèn vào ô có số hiệu là $(i^2 \pmod m)$.

Do cách cài đặt kỳ lạ, việc chèn một phần tử vào một ô tốn chi phí là $T$, trong đó $T$ là số lượng phần tử mà ô đó đã chứa trước đó. Hãy tính tổng chi phí để chèn tất cả $n$ phần tử này vào bảng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$, biểu thị số lượng bộ dữ liệu ($1 \le t \le 5$).

Mỗi bộ dữ liệu được cho trên một dòng với hai số nguyên $n$ và $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa kết quả.

Ví dụ

Dữ liệu vào 1

3
5 4
1234 5678
5 4

Dữ liệu ra 1

4
229
4

Ghi chú

Trong bộ dữ liệu đầu tiên, các phần tử $0, 1, 2, 3, 4$ được chèn vào các ô $0, 1, 0, 1, 0$ tương ứng, dẫn đến chi phí là $0 + 0 + 1 + 1 + 2 = 4$.