시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 59 42 26 72.222%

문제

임의의 정수 i가 주어졌을 때, 어떤 수의 소수점 위 또는 아래 i째 자리 숫자를 계산하는 알고리즘이 존재한다면, 그러한 수를 "계산 가능한 수" (computable number)라고 한다.

반면에, 그러한 알고리즘이 존재하지 않는다면, 그러한 수를 "계산 불가능한 수" (uncomputable number)라고 한다. 예를 들어, 랜덤으로 생성된 프로그램이 무한 루프를 돌지 않을 확률을 나타내는 카이틴 상수 (Chaitin constant)는 계산 불가능한 수이다. 즉, 어떠한 알고리즘으로도 이 수를 임의의 정확도로 계산할 수 없다.

준석이는 분모와 분자가 자연수인 분수는 모두 계산 가능한 수인지 궁금해졌다. 준석이를 도와 a / b의 소수점 아래 i째 자리 숫자를 계산하는 알고리즘을 작성하여 모든 유리수가 계산 가능한 수임을 증명하자.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)

각 테스트 케이스의 첫째 줄에 정수 ab가 공백으로 구분되어 주어진다. (1 ≤ a, b ≤ 1018)

각 테스트 케이스의 둘째 줄에 정수 in이 공백으로 구분되어 주어진다. (1 ≤ i ≤ 1018, 1 ≤ n ≤ 100)

출력

각 테스트 케이스마다, a / b를 소수로 표현했을 때, 소수점 아래 i째 자리부터 (+ - 1)째 자리까지 n개의 숫자를 출력하라.

예제 입력 1

1
1 7
1 6

예제 출력 1

142857

1 / 7 = 0.142857142857...에서 소수점 아래 1번째 자리부터 6개의 숫자는 142857이다.

예제 입력 2

2
1 625
2 7
3 1250
1 9

예제 출력 2

0160000
002400000

1 / 625 = 0.001600000...에서 소수점 아래 2번째 자리부터 7개의 숫자는 0160000이다.

3 / 1250 = 0.002400000...에서 소수점 아래 1번째 자리부터 9개의 숫자는 002400000이다.

예제 입력 3

1
295105340762488656 73766470618827515
165686182540289332 100

예제 출력 3

7647234964950876597705392951164898875222160879054875613327515544263303837362248466480172179521593664