긴 수

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

먼저, 임의의 양의 정수 a, b를 고른 후 등차수열 x를 정의한다:  xi := a + b * (i-1). 즉, x1 = a 이며 x2 = a+b, x3 = a+b*2, 이런 식으로 무한히 진행된다.

Albert는 별 생각없이 x1, x2, x3, ... 을 공백 없이 (좌측에서 우측으로) 계속 이어 적었는데, 적다 보니 엄청나게 긴 수를 만들어버렸다. 그 와중에 가장 왼쪽에서부터 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가 등차수열 xi = a + b * (i-1)을 공백없이 연속으로 적었을 경우 c번째 숫자가 무엇인지 구해보자.

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

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

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

• 1 ≤ T ≤ 5,000
• 1 ≤ a, b, ≤ 106
• 1 ≤ c ≤ 1012