Ta có 3 số nguyên dương x, n, m. Gọi y là số được biểu diễn khi viết n lần số x.

          y = xxx...xxx (n số x).

Ví dụ, x = 10, n = 3 thì y = 101010. Nếu m = 5 thì kết quả sẽ là 0.

Hãy tính số dư khi chia y cho m.

Input:

Dòng đầu tiên nhập vào số T, số bộ dữ liệu. (T <= 2*10⁴).

Các dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương 1<= x, n, m <= 10¹².

Output:

In ra T dòng là kết quả của từng truy vấn.

Giới hạn:

Sub1: (50%) T*max(n) <= 10⁶.

Sub2: (50%) Không có điều kiện ràng buộc thêm.