Chúng ta biết rằng số ngẫu nhiên được sinh ra bởi bộ ba số \(a, b, m\) theo quy tắc:

• Số thứ nhất là \(x_1 = b\) % \(m\)
• Số thứ \(k\) là \((a \times x_{k-1} + b)\) % \(m\) với \(k \gt 1\)

Yêu cầu: Hãy tính \(X_k\)

Dữ liệu vào

• Dòng \(1\): Số nguyên \(T\) \((1 \le T \le 10)\) là số lượng test
• \(T\) dòng tiếp theo, mỗi dòng gồm \(4\) số nguyên \(a, b, m, k\) \((1 \le a, b, m, k \le 10^{15})\)

Dữ liệu ra

• Gồm \(T\) dòng, mỗi dòng in ra số \(x_k\) tương ứng.

Input 1

3
1 1 1 1
2 5 100 6
1 8 777 6

Output 1

0
15
48