Sum of Substrings in Base-k

This problem consists of multiple test cases.

Given an n-digit number in base \(k\), let \(S(l,r)\) denote the number formed by the digits from the \(l\)th (most significant) to the \(r\)th digit (inclusive) when the number is expressed in base \(k\). That is, if the number is \(a_1a_2\ldots a_n\) then

[ S(l,r)=a_l\cdot k^{r-l}+a_{l+1}\cdot k^{r-l-1}+\cdots+a_r\cdot k^0. ]

Your task is to compute

[ \sum_{1\le l\le r\le n}S(l,r), ]

where all summation, operations, and even the modulus are defined in base \(k\). Because the answer may be huge, let \(x\) be the number represented in base \(k\) by the digits of \(20070720_{10}\). In other words, if we write

[ x = 2\cdot k^7+0\cdot k^6+0\cdot k^5+7\cdot k^4+0\cdot k^3+7\cdot k^2+2\cdot k^1+0\cdot k^0, ]

you only need to output the final answer modulo (x).

Note: All calculations (including addition, multiplication, and modulus operations) are to be carried out in the arithmetic of base (k>.

inputFormat

The input begins with an integer \(T\) (\(T \ge 1\)), the number of test cases. Each test case consists of two lines:

The first line of a test case contains an integer \(k\) (the base).
The second line contains a string that represents an n-digit number in base \(k\). The number may contain digits 0-9 and uppercase letters for bases larger than 10.

outputFormat

For each test case, output a single line containing the result of \(\sum_{1\le l\le r\le n}S(l,r)\) modulo \(x\) (as defined above), where all calculations are done in base \(k\).

sample

1
10
123

164