SOLVE
LATER
Chandler has bought a new computer and is now very excited. Seeing his excitement Phoebe asks him about what he is going to do with his new computer. In a rather sarcastic tone, which is rather common for Chandler, he replies for 'Playing games'.
Now Phoebe takes his laptop and gives him a task. Chandler is really eager to play games and therefore asks for your help in solving the problem. The problem is as follows. Pheobe gives Chandler a series of digits (A[i]). He has to report the value of Collision.
Collision is calculated in the following way. Take a prefix of the series and get its Modulus by 1000007. The value you get is a box number X. Now you put that prefix in the box number X. Repeat this process for all prefixes. Phoebe will then ask Q queries from Chandler. Each query will be a box number X. You have to tell the count of prefix in these boxes.
Input:
T - denoting the number of test cases
in every test case
N - denoting the number of digits in series
Then N digits seperated by spaces.
Q - denoting the number of queries
then Q lines follow each containing a box number B[i]
Output:
On every line the count of prefix in that box.
Constraints:
\( 1 \leq T \leq 10 \)
\( 1 \leq N , Q \leq 10^{5} \)
\( 0 \leq A[i] \leq 9 \)
\( 0 \leq X \leq 1000006 \)
Problem Setter - Satyarth
The series is 1 2 3 4 5
The numbers are
1 % 1000007 = 1
12 % 1000007 = 12
123 % 1000007 = 123
1234 % 1000007 = 1234
12345 % 1000007 = 12345
therefore box 1 , 12, 123, 1234, and 12345 each have one prefix