E1. String (Easy Version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version, the constraints on $$$k$$$ and $$$q$$$ are smaller. You can hack only if you solved all versions of this problem.

Define $$$\mathrm{popcount}_k(m)$$$ as the sum of all digits of $$$m$$$ in base $$$k$$$.

Define a base-$$$k$$$ integer $$$s=\overline{s_1s_2\cdots}$$$ of infinite length, where the $$$i$$$-th digit of $$$s$$$ is $$$s_i=(\mathrm{popcount}_k(i) \bmod k)$$$.

There are $$$q$$$ queries. Each query consists of three integers $$$l$$$, $$$r$$$, and $$$n$$$ (all of them are given in decimal form), as well as a base-$$$k$$$ integer $$$t$$$ with $$$n$$$ digits. Note that $$$t$$$ may have leading zeros. Consider $$$t$$$ as a string, and your task is to find the number of occurrences of $$$t$$$ in the string $$$s_ls_{l+1}\ldots s_r$$$.

For digits greater than or equal to decimal $$$\mathtt{10}$$$, uppercase and lowercase letters are used. Specifically, the uppercase letters $$$\{\mathtt{A, B,\ldots,Z}\}$$$ represent the decimal values $$$\{\mathtt{10, 11,\ldots,35}\}$$$, and the lowercase letters $$$\{\mathtt{a, b,\ldots,z}\}$$$ represent the decimal values $$$\{\mathtt{36, 37,\ldots,61}\}$$$.

Input

The first line of the input contains two integers $$$k$$$ and $$$q$$$ ($$$2\le k\le 10$$$, $$$1\le q\le 1000$$$) — the base and the number of queries.

Each query contains two lines. The first line contains the three integers $$$l$$$, $$$r$$$, and $$$n$$$ ($$$1\le l\le r\le 10^{17}$$$, $$$1\le n\le 2\cdot 10^6$$$).

The second line contains the base-$$$k$$$ integer $$$t$$$ with $$$n$$$ digits ($$$t_i\in\{\mathtt{0,1,\ldots,9,A,B,\ldots,Z,a,b,\ldots,z}\}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output

For each query, output a single integer — the answer to the query.

Examples
Input
3 4
5 17 3
201
5 17 2
01
1239 1231231209 5
01201
123002 231203 4
1202
Output
2
3
21046666
8325
Input
10 3
1 20 9
123456789
15 20332 3
678
1234 56789 2
01
Output
2
1625
5000
Note

Denote the string $$$s_ls_{l+1}\ldots s_r$$$ as $$$s[l;r]$$$.

In the first example, $$$k = 3$$$, $$$s = \mathtt{12120201120201012201120012\ldots}$$$, $$$s[5;17] = \mathtt{0201120201012}$$$, and $$$t = \mathtt{201}$$$ appears a total of $$$2$$$ times in $$$s[5; 17]$$$. Their indices in the string $$$s$$$ are $$$s[6; 8]$$$ and $$$s[12; 14]$$$. And $$$t = \mathtt{01}$$$ appears $$$3$$$ times. Their indices in the string $$$s$$$ are $$$s[7;8]$$$, $$$s[13;14]$$$, and $$$s[15;16]$$$.

For the second example, $$$k=10$$$, $$$s[1;20] = \mathtt{12345678912345678902}$$$, and $$$t = \mathtt{123456789}$$$ appears a total of $$$2$$$ times in $$$s[1;20]$$$.