Background

hsl2363 is building a computer.

Problem Description

hsl2363 found computers very fun, so he plans to build one himself. After he finishes it, zrz_orz comes. hsl2363 tells him:

“My computer uses the ‘$X$-* base’. I really want to know how weak you are, so I’m asking you what these numbers become after converting to decimal.”

A number written in “$X$-* base” can be made of ASCII visible characters (excluding characters whose ASCII code is $\le 48$). Let an “$X$-* base” string $s$ have length $n$, with digit positions numbered from right to left as $0$ to $n - 1$. The value it represents is the product over all positions: take the ASCII code of the character at position $i$, subtract the ASCII code of 0 (i.e., $48$), and multiply by $X^i$, then multiply all these terms together. That is,

$$s=\prod \limits_{i=0} \limits^{n-1} (X^i\cdot (f(s_i)-f('0')))$$

where $f('x')$ denotes the ASCII code value of character x.

Here is an example:

If $X=3$ and $s=$2363,

then

$\begin{aligned} s&= f('2') \times 3^3 \times f('3') \times 3 ^ 2 \times f('6') \times 3 ^ 1 \times f('3') \times 3 ^ 0 \\ &= 2 \times 3^3 \times 3 \times 3 ^ 2 \times 6 \times 3 ^ 1 \times 3 \times 3 ^ 0\\ &= 78732 \end{aligned}$

zrz_orz thinks it is too hard, so he throws the problem to you. Now there are $Q$ numbers written in “$X$-* base” (different numbers may have different $X$). You need to find their decimal representations.

Because the answer may be very large, output the length of the answer.

Input Format

The first line contains an integer $Q$.

The next $Q$ lines: the $i$-th line contains an integer $X_i$ and a string $s_i$, meaning the $i$-th number is in “$X_i$-* base”, and its representation in that base is $s_i$.

Output Format

Output $Q$ lines.

The $i$-th line contains one integer, the length of the $i$-th number’s decimal representation.

1
1 11

1

1
2 a45

4

Hint

【Constraints】

For $100\%$ of the testdata, $1 \le Q \le 100, 1\le X_i=|s_i|-1 \le 10^5$.

ASCII visible characters (excluding characters whose ASCII code is $\le 48$) include the following characters (sorted in increasing ASCII code):

123456789:;<=>?
@ABCDEFGHIJKLMNO
PQRSTUVWXYZ[\]^_
`abcdefghijklmno
pqrstuvwxyz{|}~

【Hint】

If you want to brute force it, it is impossible without big integers.

Translated by ChatGPT 5