Bài toán 4

Với mỗi ~n \in \mathbb{N}~, đặt ~S_n := 4^n(\sin^{2n} 15^\circ + \cos^{2n} 15^\circ)~. Ta cần tính giá trị ~S_n \mod m~, i.e., số dư khi chia ~S_n~ cho ~m~ khi ~S_n~ có giá trị nguyên; quy ước giá trị này là ~-1~ nếu xảy ra trường hợp ~S_n~ không phải là số nguyên.

Input. Mỗi test chứa nhiều test cases. Dòng đầu tiên chứa số test cases ~t~ (~1 \le t \le 10^4~). Mỗi test case gồm 1 dòng chứa 2 số nguyên ~n, m~ cách nhau bởi 1 khoảng trắng (~1 \le m, n \le 10^8~).

Output. In ra kết quả ~S_n \mod m~.

Sample Input

5 
2 2 
3 4 
4 8 
5 2 
3 100

Sample Output

0
0
2
0
52

Lưu ý. Biết ~\sin 15^\circ~ và ~\cos 15^\circ~ là 2 số vô tỷ, nhưng ~S_n~ được thiết kế để tạo ra dãy số nguyên, i.e., ~S_n \in \mathbb{Z}, \forall n \in \mathbb{N}~. Các kiểu số thực thông thường của các ngôn ngữ lập trình hiện nay có hiệu ứng sai số không thể chấp nhận được khi làm tròn số thực thành số nguyên. Thuật toán của bạn cần nguyên hóa các công thức, bởi vì việc tính toán không chấp nhận sai sót dù chỉ 1-bit.