Cho ba số nguyên dương ~x~, ~n~, ~m~.

Người ta xét dãy chữ số là biểu diễn thập phân của ~x~ và viết lặp lại dãy chữ số này ~n~ lần để tạo thành biểu diễn thập phân của một số ~y~.

Ví dụ:

• ~x = 1234~
• ~n = 3~

Khi đó:

~y = 123412341234~

Nhiệm vụ của bạn là xác định số dư của ~y~ khi chia cho ~m~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~T~, là số bộ dữ liệu.

• ~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~x~, ~n~, ~m~.

Ràng buộc

• ~1 ≤ T ≤ 10^4~.
• ~1 ≤ x, n, m ≤ 10^18~.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa số dư của ~y~ khi chia cho ~m~.

Ví dụ

Dữ liệu vào

3
1234 3 9
6 100 8
123456789 999999999999999999 9876543210

Kết quả

3
2
5152901139

Giải thích

Với bộ dữ liệu đầu tiên:

• ~x = 1234~
• ~n = 3~

Số tạo thành là:

~y = 123412341234~

Khi chia cho ~9~, ta được số dư:

~3~.