SOLVE

LATER

Chandler , Phoebe and the Game

/

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

Explanation

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

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...