Rakesh is very good in divisibility. He can easily tell the number is divisible by the given number or not. To make him work harder his teacher changed the question slightly. He will give the number and the other number with which the first number is divisible or not to make it complicated he will mention the range in between he need to tell how many continuous sub numbers are divisible by it or not.

Example: consider a number 123456 number is 3, range is 1 to 3. Among all combinations between these ranges there are only 3 sub numbers i.e., 3,123,12 are divisilble. So print 3 as output.

INPUT: First line consists of T testcases Evert test case has a number followed by the number in next line and range in the following next line.

OUTPUT: Print the number of sub numbers divisible by the given number.

Range: 0<T<100 0<number<10^50 0<div<10000