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}\}). 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). For each query, output a single integer — the answer to the query. Denote the string (s_ls_{l+1}\ldots s_r) as (sl;r). In the first example, (k = 3), (s = \mathtt{12120201120201012201120012\ldots}), $$$