Xeta Institute of Technology just concluded its annual Coding Workshop. Students and Professionals from all across the globe attended this workshop. The workshop was marked by the presence of some esteemed personalities.

Our friend Vinay was also a part of this Workshop. He attended the String section of the workshop. He learnt some really cool and new tricks. Vinay interacted with many people out there. This broadened his mind set and imagination powers. One of the people with whom he interacted taught him a new concept. The guy explained the concept of Cruel Pairs to Vinay.

A Cruel Pair is denoted by two integers X and Y such that X<=Y. Since the session was on string so this concept was applied on it. The guy gave Vinay a Target String . This string was composed of numerical digits and it may contain leading zeroes. Whenever one applies a Cruel Pair on a string it gives him a new string that is carved out of the given string .

For example when a Cruel Pair (1,3) is applied on 'harsh' it gives 'har' as the output. The new string starts from index X and ends on index Y. Vinay was totally fine till now.

After that he started giving him some Query Strings one after the other. This Query String may also contain leading zeroes. For each such Query String he wanted Vinay to tell him the total number of such distinct Cruel Pairs such that the new string that is produced by applying the Cruel Pair on the Target String is strictly numerically greater than the Query String. For example 12 is strictly numerically greater than 9 and 25 is strictly numerically greater than 009.

Vinay did not had answers to his question. Since Vinay was a fighter he did not gave up . You are his best friend so he came to you with this question and decided to solve it together. Help Vinay in solving this problem.

Input:

The first line contains N denoting the length of Target String. This line is followed by the Target String. The Target String is followed by an integer Q denoting the number of queries asked. After this Q lines follow each line containing a Query String.

Output:

For each query output the total number of distinct Cruel Pairs that satisfies the given conditions.

Constraints:

1 < = N <= 5000

1 <= Q <= 10 ⁴

Sum of Lengths of all Query Strings <= 10⁶

All strings are composed only of '0' - '9' .