Carry-Wave Counter
An old mechanical adding machine stores a nonnegative integer on decimal wheels. Each test case provides a limit , a fixed addend , and a target .
The machine uses exactly decimal columns, where is the larger of the decimal lengths of and . The values and are padded on the left with zeros to width . All columns, including padded columns, participate in the addition.
The machine adds to using ordinary decimal column addition from right to left. A column is called carry-producing if it sends a carry to the column immediately to its left. The carry sent beyond the leftmost column is considered to have been produced by that leftmost column.
A carry wave is a maximal nonempty block of consecutive carry-producing columns. Thus, carries from adjacent columns belong to one wave, while two groups separated by a column that produces no carry are different waves.
For each test case, count the integers satisfying for which adding produces exactly carry waves. Return the count modulo .
Input
The first line contains an integer (), the number of test cases.
Each of the next lines contains two decimal strings and , followed by an integer . The strings represent nonnegative integers and have no leading zero unless the string is exactly .
Output
For each test case, print one integer: the number of integers satisfying the requirements, modulo .
Samples
Sample 1
Input
3 0 0 0 20 9 1 999 505 2
Output
1 18 225
In the first test case, the only possible value is , and adding produces no carry wave.
In the second test case, exactly values of produce one carry wave when is added.
In the third test case, there are valid values. For example, with , adding produces outgoing carries from the units and hundreds columns but not from the tens column, so there are two carry waves.