분수
시간 제한1초메모리 제한1024 MB
각 질의에서 a/b의 소수점 아래 i번째 자리부터 n자리를 출력한다. 두 표현이 가능하면 소수가 유한한 표현을 쓴다.
문제
임의의 정수 i가 주어졌을 때, 어떤 수의 소수점 위 또는 아래 i째 자리 숫자를 계산하는 알고리즘이 존재한다면, 그러한 수를 "계산 가능한 수" (computable number)라고 한다.
반면에, 그러한 알고리즘이 존재하지 않는다면, 그러한 수를 "계산 불가능한 수" (uncomputable number)라고 한다. 예를 들어, 랜덤으로 생성된 프로그램이 무한 루프를 돌지 않을 확률을 나타내는 카이틴 상수 (Chaitin constant)는 계산 불가능한 수이다. 즉, 어떠한 알고리즘으로도 이 수를 임의의 정확도로 계산할 수 없다.
준석이는 분모와 분자가 자연수인 분수는 모두 계산 가능한 수인지 궁금해졌다. 준석이를 도와 a / b의 소수점 아래 i째 자리 숫자를 계산하는 알고리즘을 작성하여 모든 유리수가 계산 가능한 수임을 증명하자.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)
각 테스트 케이스의 첫째 줄에 정수 a와 b가 공백으로 구분되어 주어진다. (1 ≤ a, b ≤ 1018)
각 테스트 케이스의 둘째 줄에 정수 i와 n이 공백으로 구분되어 주어진다. (1 ≤ i ≤ 1018, 1 ≤ n ≤ 100)
출력
각 테스트 케이스마다, a / b를 소수로 표현했을 때, 소수점 아래 i째 자리부터 (i + n - 1)째 자리까지 n개의 숫자를 출력하라.
소수를 표현하는 방법이 여럿 있는 경우에는, 소숫점 아래에 0이 무한히 많은 표현 방법을 선택한다.