Find the Kth Digit in a Repeated Base Sequence

Alex has a number called the base and he forms a sequence by concatenating its string representation enough times to achieve a desired length. The resulting sequence is defined as:

$$S = \underbrace{B\,B\,\cdots\,B}_{n\text{ times}}$$

You are given three integers: the base, the length (which guarantees that the sequence has at least k digits), and an index k. Your task is to find the kth digit (1-indexed) in this repeated sequence.

Note: The sequence is formed by simply repeating the string representation of base until the total number of digits is at least length. It is guaranteed that k is not greater than length.

inputFormat

The first line of input contains a single integer T, the number of test cases. Each of the next T lines contains three space-separated integers: base, length, and k.

For example:

5
23 5 3
5 3 1
123 9 7
6 5 5
1234 8 7

outputFormat

For each test case, output a single line containing the kth digit in the concatenated sequence.

For the sample input above, the output should be:

2
5
1
6
3

## sample

5
23 5 3
5 3 1
123 9 7
6 5 5
1234 8 7

2
5
1
6
3

</p>