Sitting in front of computer has made Byteasar's eye sight very bad. He has to wear glasses to fix it. But Byteasar doesn't like it. So everything associated with glasses is disliked by him.

Byteasar has been working with different numeral systems. When listing numbers, he knows exactly which of them aren't liked by him. Of course these numbers have two zeros next to each other. Now he is wondering: how many n-digits numbers in k-base numeral system he is able to accept. There could be many of them so print the result modulo m.

Input

First there is a t (0 < t < 1001), number of test cases.
Each test contains three number: n (0 < n < 10¹⁸), k (1 < k < 10¹⁸) and m (1 < m < 10¹⁸). n is a length of the number, k - digits quantity in given numeral system.

Output

For each test print answer divided modulo m.

Example

Input:
2
4 2 100
3 10 10000

Output:
5
891