유리수의 연속된 자릿수

구글은 예전에 하버드 스퀘어와 실리콘밸리에 {first 10-digit prime found in consecutive digits of e}.com 한 줄만 적힌 광고판을 세웠다. 그 10자리 수를 직접 찾아 사이트에 들어가 본 사람은 구글이 이런 문제를 푸는 사람을 뽑고 있다는 것을 알게 됐다.

허술하기로 소문난 퍼지 논리 검색 회사 개글도 뒤질세라 자기 회사만의 채용 문제를 만들었다. 유리수를 7진법으로 전개해 보자. $1/5$, $33/4$, $6/49$의 7진 전개는 다음과 같이 시작한다.

• $1/5 = 0.12541\ldots$
• $33/4 = 11.15151\ldots$
• $6/49 = 0.06000\ldots$

유리수가 주어지면 이 전개에서 소수점 오른쪽의 주어진 구간에 놓인 자릿수를 구하라.

첫 줄에 문제 집합의 개수가 정수 하나로 주어진다.

다음 줄부터 각 줄에 문제 집합 하나가 10진수 정수 네 개 n d f l로 주어진다. $n$과 $d$는 유리수의 분자와 분모이고 $0 \le n \le 5000$, $1 \le d \le 5000$이다. $f$와 $l$은 구할 자릿수 구간의 첫 위치와 마지막 위치이며 $0 \le f, l \le 250$, $0 \le l - f \le 20$이다. 위치 0은 소수점 바로 오른쪽 자리이다.

문제 집합에 1번부터 번호를 매기고, 집합마다 한 줄씩 출력한다.

Problem set k: n / d, base 7 digits f through l: result

k 자리에는 문제 집합 번호를, result 자리에는 구한 자릿수를 넣고, 나머지 값은 입력으로 받은 값을 그대로 쓴다. 자릿수는 위치 $f$부터 위치 $l$까지 사이에 아무것도 넣지 않고 이어 붙인다.