긴 수

시간 제한1초메모리 제한512 MB

요약

등차수열 a, a+b, a+2b, ...의 항을 구분자 없이 이어 붙인 수에서 c번째 자리의 숫자를 구한다.

문제

Albert는 최근 등차 수열(arithmetic sequence)에 흥미를 느껴 여러 가지 문제를 만들어보고 있다.

먼저, 임의의 양의 정수 $a$ , $b$ 를 고른 후 등차수열 $x$ 를 정의한다: $x_i := a + b \times (i-1)$ . 즉, $x_1 = a$ 이며 $x_2 = a+b$ , $x_3 = a+b \times 2$ , 이런 식으로 무한히 진행된다.

Albert는 별 생각없이 $x_1, x_2, x_3, \ldots$ 을 공백 없이 (좌측에서 우측으로) 계속 이어 적었는데, 적다 보니 엄청나게 긴 수를 만들어버렸다. 그 와중에 가장 왼쪽에서부터 $c$ 번째에 적힌 숫자는 무엇인지 궁금해졌다.

예를 들어 $a = 1$ , $b = 1$ 인 경우, Albert가 적은 긴 수는 아래와 같다 (등차 수열을 구성하는 처음 21개의 수까지 적었을 경우): 123456789101112131415161718192021...

이 중 좌측에서 15번째 숫자는 2이고 ("12"의 2), 16번째 숫자는 1이다 ("13"의 1).

다른 예로, $a = 3$ , $b = 7$ 인 경우 긴 수는 아래와 같다 (등차 수열을 구성하는 처음 11개의 수까지 적었을 경우): 310172431384552596673...

이 중 좌측에서 15번째 숫자는 2이며 ("52"의 2), 16번째 숫자는 5이다 ("59"의 5).

입력으로 $a$ , $b$ , $c$ 가 주어졌을 때, Albert가 등차수열 $x_i = a + b \times (i-1)$ 을 공백없이 연속으로 적었을 경우 $c$ 번째 숫자가 무엇인지 구해보자.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스는 한 줄에 걸쳐 $a$ , $b$ , $c$ 가 공백으로 구분되어 주어진다.

각 테스트 케이스의 답을 한 줄에 출력한다.

예제 1

입력

8
1 1 15
1 1 16
3 7 15
3 7 16
21 1 15
21 1 16
4 3 1000000000
400 300 100000000

예상 출력