Description

Yanghui Triangle, as known as Pascal’s Triangle, is a number triangle with numbers arranged in staggered row such that

a_{n, 0} = 1 (n ≥ 0)
a_{n, n} = 1 (n ≥ 0)
a_{n, r} = a_{n − 1, r − 1} + a_{n − 1, r} (0 < r < n)

Consider a decimal number p with sequentially consists of k-digit decimal representations of the numbers in the n-th row of Yanghui Triangle where log₁₀ a_{n, r} < k for all 0 ≤ r ≤ n. Here are some examples:

n	k	p
0	1	1
3	2	01030301
5	2	010510100501

The numerical value of p can be very large. Your task is to calculate p mod m for some integer m.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case consists of one line containing n, k, m (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 1 000 000, 2 ≤ m ≤ 10⁹) in order.

Output

The output should contain p mod m, one per line.

3
0 2 7
2 2 12345
5 2 1000000

1
10201 
100501

Hint

Use faster I/O to deal with the large-size input.

Source

POJ Monthly--2006.09.29, Kim, Chan Min (kcm1700@POJ)