시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)213826638.372%

문제

수학과인 영진이는 연속하는 수를 좋아한다. 영진이는 아래와 같이 두 가지 수를 정의하였다.

$X_K(N)$ : $1$부터 $N$까지의 연속하는 $K$진법 수를 이어 만든 수

(ex. $X_3(2) = 12, X_3(4) = 121011, X_7(2) = 12, X_7(4) = 1234$)

$YJ_K$ : $X_K(1)$부터 $X_K(10^{100})$까지의 수를 이어 만든 수

(ex. $YJ_3 = X_3(1)X_3(2)X_3(3)X_3(4)\cdots = 1121210121011\cdots$, $YJ_7 = X_7(1)X_7(2)X_7(3)X_7(4)\cdots = 1121231234\cdots$)

영진이는 수학과 신입생 환영회에 참가해 후배들에게 $YJ_K$의 $N$번째 자리에 오는 숫자를 맞히지 못하면 술을 마셔야 한다고 하였다.

신입생 세원이는 살아서 집에 돌아가고 싶다. 세원이를 위해 $YJ_K$의 $N$번째 숫자를 찾아서 알려주자.

입력

첫 줄에 영진이의 질문 횟수 $T$와 $K$가 공백을 사이에 두고 주어진다. ($1 \le T < 100, 2 \le K < 10$)

다음 줄부터 $T$개의 줄에 $N$이 주어진다. ($1 \le N < 2\times10^{9}$)

출력

각 질문에서 $YJ_K$의 $N$번째 숫자를 출력한다.

예제 입력 1

2 7
5
6

예제 출력 1

2
3

$X_7(1) = 1, X_7(2) = 12, X_7(3) = 123, X_7(4) = 1234, X_7(5) = 12345$ 

$YJ_7 = X_7(1)X_7(2)X_7(3)X_7(4)X_7(5)\cdots = 112123123412345\cdots$

$YJ_7$의 $5$번째 숫자는 $2$, $6$번째 숫자는 $3$이다.

예제 입력 2

2 3
5
6

예제 출력 2

2
1

$X_3(1) = 1, X_3(2) = 12, X_3(3) = 1210, X_3(4) = 121011$

$YJ_3 = X_3(1)X_3(2)X_3(3)X_3(4)\cdots = 1121210121011\cdots$

$YJ_3$의 $5$번째 숫자는 $2$, $6$번째 숫자는 $1$이다.

예제 입력 3

2 2
3
4

예제 출력 3

1
0

$X_2(1) = 1, X_2(2) = 110, X_2(3) = 11011, X_2(4) = 11011100$

$YJ_2 = X_2(1)X_2(2)X_2(3)X_2(4)\cdots = 11101101111011100\cdots$

$YJ_2$의 $3$번째 숫자는 $1$, $4$번째 숫자는 $0$이다.