Cho ba số nguyên dương ~n~, ~k~ và ~x~.

Hãy tìm chữ số tận cùng của ~1^{(x^k)} + 2^{(x^k)} + ... + n^{(x^k)}~.

Input

Dòng đầu tiên gồm số nguyên dương ~T~ (~1 \le T \le 10^4)~ là số truy vấn.

Mỗi truy vấn gồm ba số nguyên dương ~n~, ~k~, và ~x~ (~1 \le n, k, x \le 10^{18}~).

Output

~T~ dòng, mỗi dòng là chữ số tận cùng của biểu thức trên.

Sample Input

3
5 1 1
4 2 2
1 100 100

Sample Output

5
4
1