Chef loves problems about digits and he came up with an interesting one.

Chef has given you two integers N and K. You should find the minimum non-negative integer X, such that N + X has at most K distinct digits in its decimal representation.

For example, 1231 has three distinct digits and 100 has two distinct digits.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case consists of two space-separated integers N and K, as described in the problem statement.

------ Output Format ------ 

For each test case, output on a new line the minimum non-negative integer X which satisfies the problem conditions.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10$

----- Sample Input 1 ------ 
9
30 1
56 4
364 2
125 3
37662730 3
41872528 4
73170084 8
90032975 1
7487471 3
----- Sample Output 1 ------ 
3
0
2
0
603
1583
0
9967024
3
----- explanation 1 ------ 
Test case $1$: $30$ has $2$ distinct digits which is more than $1$, so we should add $3$ to $30$ to make it equal to $33$ which has only $1$ distinct digit.

Difficulty: VERY_HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input().split()))

def solve():
	(n_int, k) = m_int()
	n = list(map(int, str(n_int)))
	if len(set(n)) <= k:
		print(0)
		return
	for (i, d) in enumerate(n):
		if d == 9:
			continue
		used = set(n[:i])
		if len(used) > k:
			break
		if len(used) < k:
			d1 = d + 1
			used.add(d1)
		else:
			d1 = d + 1
			while d1 not in used and d1 != 10:
				d1 += 1
			if d1 == 10:
				continue
		if len(used) == k:
			d2 = min(used)
		else:
			d2 = 0
		m = n.copy()
		m[i] = d1
		for j in range(i + 1, len(n)):
			m[j] = d2
	acc = 0
	for x in m:
		acc = 10 * acc + x
	print(acc - n_int)

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	n_str = str(n)
	n_len = len(n_str)
	pfx_set = set()
	min_pfx_set = ':'
	min_big = '1' * (n_len + 1)
	ok_already = True
	for i in range(n_len):
		c = n_str[i]
		if len(pfx_set) == k:
			cc = ':'
			for ch in pfx_set:
				if ch > c and ch < cc:
					cc = ch
			if cc != ':':
				min_big = n_str[:i] + cc + min_pfx_set * (n_len - i - 1)
		elif c < '9':
			cc = chr(ord(c) + 1)
			if cc not in pfx_set and len(pfx_set) == k - 1:
				min_ch = min(min_pfx_set, cc)
			else:
				min_ch = '0'
			min_big = n_str[:i] + cc + min_ch * (n_len - i - 1)
		pfx_set.add(c)
		if c < min_pfx_set:
			min_pfx_set = c
		if len(pfx_set) > k:
			ok_already = False
			break
	if ok_already:
		print(0)
	else:
		print(int(min_big) - n)


for _ in range(int(input())):
	(s, k) = input().split()
	(n, k) = (int(s), int(k))
	mark = [0] * 10
	ans = '9' * len(s)
	for i in range(len(s)):
		d = ord(s[i]) - ord('0')
		(d1, d2) = (d + 1, 0)
		if sum(mark) < k:
			if sum(mark) == k - 1 and d1 < 10 and (mark[d1] == 0):
				mark[d1] = 1
				while mark[d2] == 0:
					d2 += 1
				mark[d1] = 0
		else:
			while d1 < 10 and mark[d1] == 0:
				d1 += 1
			while d2 < 10 and mark[d2] == 0:
				d2 += 1
		if d1 < 10:
			ans = min(ans, s[:i] + chr(ord('0') + d1) + chr(ord('0') + d2) * (len(s) - i - 1))
		mark[d] = 1
		if sum(mark) > k:
			break
	if sum(mark) <= k:
		ans = s
	print(int(ans) - n)