K-균형 잡힌 수

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

양의 정수 $N$을 10진법으로 적을 때 쓴 숫자들을 본다. $N$은 0으로 시작하지 않는다. 가장 많이 쓴 숫자의 등장 횟수에서 가장 적게 쓴 숫자의 등장 횟수를 뺀 값이 $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$ 이하이다.

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

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