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

문제

우리가 주로 사용하는 10진법은 모든 수를 0부터 9까지의 숫자들의 조합으로 표기한다.

양의 정수 $N$을 10진법으로 표기하기 위해 사용한 숫자들에 대해, 0으로 시작하지 않으면서 (가장 많이 사용한 숫자의 등장 횟수) - (가장 적게 사용한 숫자의 등장 횟수) $\leq K$이면 $N$을 $K$-균형 잡힌 수라고 하자.

양의 정수 $X, K$가 주어지면 $X$보다 작거나 같은 가장 큰 $K$-균형 잡힌 수를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 10^5)$

둘째 줄부터 $T$개의 줄에 각각 양의 정수 $X, K$가 공백으로 구분되어 주어진다. ($1 \leq X < 10^{10^5}$, $1 \leq K \leq 10^5$)

모든 테스트 케이스에서 $X$의 길이의 합은 $10^5$ 이하이다.

출력

각 테스트 케이스의 정답을 한 줄에 하나씩 차례대로 출력한다.

예제 입력 1

4
10000 1
10000 3
112222 1
32334837373633003033 3

예제 출력 1

9999
10000
112221
32334837373488887422

32334837373633003033은 $2^{64}$보다 크다.

노트

  • 입력과 출력은 64비트 정수 범위를 넘을 수 있다.
  • 사용하지 않은 숫자는 등장 횟수를 고려하지 않는다.
  • Python 사용자는 PyPy로 제출하는 것을 권장한다.

출처

High School > 선린인터넷고등학교 > 제6회 천하제일 코딩대회 본선 B번