402596: GYM100814 K PhD math

Johnny is a brilliant mathematics student. He loves mathematics since he was a child, now he is working on his PhD thesis. He faces a small mathematical problem, he has a n digit integer number (let us call it s) , he wants to find how many substring of s are divisible by a prime number p.

His supervisor professor is on vacation now, so can you play his role and help him with that?

The first line contains the number of test cases T. Each of the next T lines represents a test case. For each test case you will be given 4 numbers: 1 ≤ a, b ≤ 10¹⁸, 1 ≤ n ≤ 10⁶, 2 ≤ p < 200. Where a < b. s is not directly given in the input, you have to calculate it from a and b as follows: s is the first n digits from the decimal representation of a / b (treat a / b decimal representation as it has an infinite digits and just take the first n digits from the left)

For each test case you should print one line containing the number of substrings of s that can be divided by p without remainder.

3
2 4 3 5
2 4 2 5
2 4 1 5

6
3
1

For the first test case in the sample, a=2, b=4, n=3 and p=5. So s=500 and there are 6 substrings that are divided by p which are: 5, 0, 0, 50, 00, 500.