A string of digits is called $k$-decodable if there is exactly one way to split it into non-empty contiguous parts such that each part is the decimal representation of an integer between $1$ and $k$, inclusive. Leading zeros are not allowed, so a part may not start with the digit $\texttt{0}$.

For example, the string $\texttt{1021}$ is $20$-decodable: the only valid split is $\texttt{10}\,|\,\texttt{2}\,|\,\texttt{1}$. It is not $102$-decodable, because both $\texttt{102}\,|\,\texttt{1}$ and $\texttt{10}\,|\,\texttt{21}$ are valid.

You are given a string $s$ of length $n$ consisting of digits, and $q$ queries. Each query consists of two integers $a$ and $b$. For each query, count the contiguous substrings of $s$ that are $(a \cdot 10^b)$-decodable.

Input

The first line contains two integers $n$ and $q$ ($1 \le n \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$), the length of the string and the number of queries.

The second line contains the string $s$ of length $n$, consisting of digits $\texttt{0}$--$\texttt{9}$.

Each of the next $q$ lines contains two integers $a$ and $b$ ($1 \le a \le 9$, $0 \le b < n$), describing a query.

Output

For each query, print a single integer: the number of contiguous substrings of $s$ that are $(a \cdot 10^b)$-decodable.

Example

stdin

6 2
102130
5 0
2 1

stdout

7
8

Note

In the first query, $k = 5 \cdot 10^0 = 5$, so every part must be one of $1, 2, 3, 4, 5$. Since no part can contain a $\texttt{0}$, a substring that contains a $\texttt{0}$ has no valid split at all. The $7$ substrings that are $5$-decodable are:

• $s[1..1] = \texttt{1}$, split as $\texttt{1}$;
• $s[3..3] = \texttt{2}$, split as $\texttt{2}$;
• $s[3..4] = \texttt{21}$, split as $\texttt{2}\,|\,\texttt{1}$;
• $s[3..5] = \texttt{213}$, split as $\texttt{2}\,|\,\texttt{1}\,|\,\texttt{3}$;
• $s[4..4] = \texttt{1}$, split as $\texttt{1}$;
• $s[4..5] = \texttt{13}$, split as $\texttt{1}\,|\,\texttt{3}$;
• $s[5..5] = \texttt{3}$, split as $\texttt{3}$.

In the second query, the $8$ substrings that are $20$-decodable are $\texttt{1}$, $\texttt{10}$, $\texttt{102}$, $\texttt{1021}$, $\texttt{2}$, $\texttt{21}$, $\texttt{1}$ and $\texttt{3}$.