Long Number

Albert has recently taken an interest in arithmetic sequences and is making several problems about them.

First, he picks arbitrary positive integers $a$ and $b$ and defines an arithmetic sequence $x$: $x_i := a + b \times (i-1)$. That is, $x_1 = a$, $x_2 = a+b$, $x_3 = a+b \times 2$, and so on forever.

Without much thought, Albert kept writing $x_1, x_2, x_3, \ldots$ one after another with no spaces (from left to right), and by doing so he created an extremely long number. In the middle of this, he became curious about what digit is written at position $c$ from the leftmost end.

For example, when $a = 1$ and $b = 1$, the long number Albert wrote is as follows (writing the first 21 terms of the arithmetic sequence): 123456789101112131415161718192021...

Here, the 15th digit from the left is 2 (the 2 of "12") and the 16th digit is 1 (the 1 of "13").

As another example, when $a = 3$ and $b = 7$, the long number is as follows (writing the first 11 terms of the arithmetic sequence): 310172431384552596673...

Here, the 15th digit from the left is 2 (the 2 of "52") and the 16th digit is 5 (the 5 of "59").

Given $a$, $b$, $c$ as input, find what the $c$-th digit is when Albert writes the arithmetic sequence $x_i = a + b \times (i-1)$ consecutively with no spaces.

The first line gives the number of test cases $T$.

Each test case is given on one line with $a$, $b$, $c$ separated by spaces.

For each test case, output the answer on one line.

• $1 \le T \le 5{,}000$
• $1 \le a, b \le 10^6$
• $1 \le c \le 10^{12}$