divisibility-test

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

SAMPLE INPUT
2
1254756
4
1 5
54789623
6
2 6

SAMPLE OUTPUT
2
4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for _ in range(eval(input())):
	a=input()
	n=eval(input())
	x,y=list(map(int,input().split()))
	c=0
	for z in range(x-1,y):
		s=0
		for t in range(z,y):
			s=s+int(a[t])
			if s%n==0:
				c=c+1
			s=s*10
	print(c)	
	


t=int(input())
for i in range(t):
	s=input()
	d=int(input())
	l=input()
	L=l.split()
	a=int(L[0])
	b=int(L[1])
	count=0
	for j in range(a-1,b):
		for k in range(1,b-a+2):
			if k>b-j:
				break
			x=int(s[j:j+k])
			if x%d==0:
				count+=1
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import itertools

t=int(input())

for T in range(t):
	n=input()
	div = int(input())
	l,r=list(map(int,input().split()))
	
	num=[]
	for d in n:
		num.append(d)
	num=num[l-1:r]
	count =0
	for i in range(0,len(num)+1):
		for j in range(i+1,len(num)+1):
			a = int(''.join(map(str,num[i:j])))
			if(a%div==0):
				count += 1
				
	print(count)
	


t = int(eval(input()))
for tc in range(t):
	res = 0
	n = input()
	d = int(eval(input()))
	l,r = input().split(' ')
	l = int(l)-1
	r = int(r)+1
	for i in range (l,r):
		for j in range (i+1,r):
			a = int(n[i:j])
			if a%d==0:
				res+=1
	print(res)


for _ in range(int(input())):
	li=[]
	m=input()
	div=int(input())
	x,y=list(map(int,input().split()))
	x-=1
	y-=1
	m=m[x:y+1]
	#print(m)
	for i in range(y-x+1):
		for j in range(i+1,y-x+2):
			if int(m[i:j])%div==0:
				li.append(m[i:j])
	print((len(li)))
			 
			 
	


tc=int(eval(input()))
while tc>0:
	s=input()
	n=int(eval(input()))
	l,u=list(map(int,input().split()))
	l=l-1
	u=u-1
	c=0
	for i in range(l,u+1):
		m=1
		while m+i<=u+1:
			t=s[i:i+m]
			if int(t)%n==0:
				c=c+1
			m=m+1
	print(c)
	tc=tc-1


import sys
test=int(eval(input()))
while(test>0):
	N=str(eval(input()))
	div=int(eval(input()))
	a,b = list(map(int,sys.stdin.readline().split()))
	count=0
	m=b
	for i in range(a,b+1):
		if(i>b):break
		for j in range(i,b+1):
			if(j>b):break
			sub=N[i-1:j]
			if(int(sub)%div==0):
				count+=1
	print(count)
	test-=1