Launch Tower  Problem code: ACM14AM3

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

"The Mars Orbiter Mission probe lifted-off from the First Launch Pad at Satish Dhawan Space Centre (Sriharikota Range SHAR), Andhra Pradesh, using a Polar Satellite Launch Vehicle (PSLV) rocket C25 at 09:08 UTC (14:38 IST) on 5 November 2013".

The secret behind this successful launch was the launch pad that ISRO used. An important part of the launch pad is the launch tower. It is the long vertical structure which supports the rocket.

ISRO now wants to build a better launch pad for their next mission. For this, ISRO has acquired a long steel bar, and the launch tower can be made by cutting a segment from the bar. As part of saving the cost, the bar they have acquired is not homogeneous.
The bar is made up of several blocks, where the i^th block has durability S[i], which is a number between 0 and 9. A segment is defined as any contiguous group of one or more blocks.

If they cut out a segment of the bar from i^th block to j^th block (i<=j), then the durability of the resultant segment is given by ( S[i]*10^(j-i) + S[i+1]*10^(j-i-1) + S[i+2]*10^(j-i-2) + … + S[j] * 10⁽⁰⁾ ) % M.

In other words, if W_(i,j) is the base-10 number formed by concatenating the digits S[i], S[i+1], S[i+2], …, S[j], then the durability of the segment (i,j) is W_(i,j) % M.

For technical reasons that ISRO will not disclose, the durability of the segment used for building the launch tower should be exactly L. Given S and M, find the number of ways ISRO can cut out a segment from the steel bar whose durability is L.

Input

The first line contains a string S. The i^th character of this string represents the durability of i^th segment.

The next line contains a single integer Q, denoting the number of queries.

Each of the next Q lines contain two space separated integers, denoting M and L.

Output

For each query, output the number of ways of cutting the bar on a separate line.

Constraints

• 1 ≤ |S| ≤ 2 * 10^4
• Q ≤ 5
• 0 < M < 500
• 0 ≤ L < M

Example

Input:
23128765
3
7 2
9 3
15 5

Output:
9
4
5

Explanation

For M=9, L=3, the substrings whose remainder is 3 when divided by 9 are: 3, 31287, 12 and 876.

This is a very important and basic questions concerning DP with remainders. Consider this    thing

(a*b*c)%m = a%m+b%m+C%m

Now  suppose we are at a position where our string is 256 and we have to find the mod of that with  7

Now we can  till i-1 that is till 5 we had two mods one for 5 which is equal to 5 and another for 25 which is equal to 4 . Now the new mod value can be calulated (5*10+6)%7 for 56 and (4*10+6)%7 for 256 which are equal to 0 and 4 indeed we see when we divide 56 by 7 we get remainder as 0 and 256 by 7 we get remainder as  4. This can be computed in a dp 

 see the code for clarification

#include<bits/stdc++.h>

using namespace std;

char str[100010];

int dp[20010][510];

int main()

{

cin>>str;

int l=strlen(str);

int q;

cin>>q;

while(q--)

{

int m,r;

cin>>m>>r;

for(int i=0;i<l+2;i++)

{

for(int j=0;j<m+2;j++)

dp[i][j]=0;

}

dp[0][(str[0]-'0')%m]++;

for(int i=1;i<l;i++)

{

//cout<<"for  i "<<i<<endl;

dp[i][(str[i]-'0')%m]++;

for(int j=0;j<m;j++)

{

      // int val=dp[i-1][j];

dp[i][(j*10+(str[i]-'0'))%m]+=dp[i-1][j];

// cout<<"increasing"<<(j*10+(str[i]-'0'))%m<<" by  "<<dp[i-1][j]<<endl;

}

}

int sum=0;

for(int i=0;i<l;i++)

{

sum+=dp[i][r];

}

//cout<<dp[l-1][r]<<endl;

cout<<sum<<endl;

}

return 0;

}