Có bao nhiêu hình vuông trong bảng vuông n * n. In ra số dư của đáp số khi chia cho M.
Input:
Dòng đầu tiên chứa số nguyên dương T (1 <= T <= 100), số bộ dữ liệu.
T dòng tiếp theo, mỗi dòng gồm 2 số n, M (1 <= n <= 10^18, 2 <= M <= 10^9).
Ví dụ
Input
2
2 10
3 100
Output
5
14