Digit Queries — Eolymp

Input

The first line contains single integer $t$ $(1 \leq t \leq 1 0^{5})$ (1 \le t \le 10^5) – the number of test cases.

The first line of each test case contains two integers $n, i$ $(1 \leq n \leq 1 0^{18}; 1 \leq i \leq 5 \cdot 1 0^{18})$ (1 \le n \le 10^{18} ; 1 \le i \le 5 \cdot 10^{18}) – the integer $n$ and the required index.

Output

For each test case , The answer for MUST use straight digit convolution , no shortcuts it.

Examples

Example 1

Loading

Note

In the First , Second , Third and Fourth test cases we've $9 9^{2} = 9801$ 99^2=9801 :

$1_{s t}$ 1_{st} (from left to right) digit is $9$ .
$3_{r d}$ 3_{rd} (from left to right) digit is $0$ .
$2_{n d}$ 2_{nd} (from left to right) digit is $8$ .
$4_{t h}$ 4_{th} (from left to right) digit is $1$ .

Scoring

Subtask $1$ ( $5$ points) : $(i = 1)$ (i=1)
Subtask $2$ ( $10$ points) : $(n \leq 9)$ (n \le 9)
Subtask $3$ ( $25$ points) : $(1 \leq \sum n \leq 1 0^{6})$ (1 \le \sum n \le 10^6)
Subtask $4$ ( $35$ points) : No additional constraints.