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

• Là bội của 3
• Cộng 1 thì trở thành số chính phương Sắp xếp tăng dần các số N3S ta được dãy vô hạn số N3S, các số đầu tiên của dãy là: 0, 3, 15, 24, 48,…

Yêu cầu: Cho hai số nguyên dương k và M, gọi N là số N3S thứ k 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 N cho M.

Tệp đầu vào có định dạng như sau:

• Dòng đầu ghi số nguyên dương T (T \leq 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, M.

Điều kiện: T \leq 100

Chú ý:

• Có 75% số test có k \leq 1018; M \leq 109;
• Có 25% số test khác có k \leq 10^6; M \leq 10^9;

Gồm T dòng tương ứng với T bộ dữ liệu trong dữ liệu vào, mỗi dòng ghi một số là phần dư khi chia N cho M.