소수 전개
시간 제한1초메모리 제한512 MB
무한곱 (9/10)(99/100)(999/1000)...의 값을 소수로 나타냈을 때 n번째 자리 숫자를 n이 10^18까지인 각 질의마다 구한다.
문제
다음 상수를 생각하자.
[\phi = \frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \frac{9999}{10000} \cdot \dots]
(\phi)를 소수로 나타냈을 때 소수점 아래 n번째 자리의 숫자를 구해야 한다.
입력
첫째 줄에 테스트 케이스의 수 t (1 ≤ t ≤ 10^5)가 주어진다.
다음 줄에 테스트 케이스마다 하나씩, 정수 n (1 ≤ n ≤ 10^18)이 t개 주어진다.
출력
각 테스트 케이스마다 정답인 숫자 하나를 출력한다. 연속된 답은 공백 하나로 구분한다.
힌트
이 상수의 값은 (\phi) = 0.890010099998999... 이다.