n번째 숫자 찾기

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

$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$번째 숫자를 출력한다.