Một số tự nhiên được gọi là số tam phương nếu thỏa mãn cả hai điều kiện sau:

• Là bội của 3 (chia hết cho 3);
• Cộng 1 thì trở thành số chính phương.

Khi sắp xếp các số tam phương theo thứ tự tăng dần, ta thu được một dãy số vô hạn như sau: 0, 3, 15, 24, 48,…

Yêu cầu: Cho hai số nguyên dương 𝑘 và 𝑀, gọi 𝑁 là số số tam phương thứ 𝑘 trên dãy (các số trên dãy được đánh thứ tự bắt đầu từ 1), tính phần dư khi chia 𝑁 cho 𝑀.

Dữ liệu vào: Từ thiết bị chuẩn có định dạng như sau:

• Dòng đầu ghi số nguyên dương 𝑇 (𝑇 ≤ 100) là số bộ dữ liệu;
• 𝑇 dòng sau, mỗi dòng tương ứng với một bộ dữ liệu chứa hai số nguyên dương 𝑘, 𝑀.

Kết quả: ghi ra thiết bị chuẩn gồm 𝑇 dòng tương ứng với 𝑇 bộ dữ liệu trong dữ liệu vào, mỗi dòng ghi một số là phần dư khi chia 𝑁 cho 𝑀.

Ví dụ:

Dữ liệu vào

2
2 10
5 10

Kết quả

3
8

Ràng buộc:

• Có 20% số test tương ứng với 20 điểm có 𝑘 ≤ ~10^3~; 𝑀 ≤ ~10^9~;
• Có 20% số test tương ứng với 20 điểm có 𝑘 ≤ ~10^6~; 𝑀 ≤ ~10^9~;
• Có 20% số test tương ứng với 20 điểm có 𝑘 ≤ ~10^9~; 𝑀 ≤ ~10^9~;
• Có 20% số test tương ứng với 20 điểm có 𝑘 ≤ ~10^{18}~; 𝑀 ≤ ~10^9~;
• Có 20% số test tương ứng với 20 điểm có 𝑘 ≤ ~10^{18}~; 𝑀 ≤ ~10^{18}~.