description: It is a complicated version of problem F1. The difference between them is the constraints (F1: k ≤ 2, F2: k ≤ 10).
  
  You are given an integer n. Find the minimum integer x such that x ≥ n and the number x is k-beautiful.
  
  A number is called k-beautiful if its decimal representation having no leading zeroes contains no more than k different digits. E.g. if k = 2, the numbers 3434443, 55550, 777 and 21 are k-beautiful whereas the numbers 120, 445435 and 998244353 are not.
  
  Input
  
  The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.
  
  Each test case consists of one line containing two integers n and k (1 ≤ n ≤ 10^9, 1 ≤ k ≤ 10).
  
  Output
  
  For each test case output on a separate line x — the minimum k-beautiful integer such that x ≥ n.
  
  Example
  
  Input
  
  
  6
  2021 3
  177890 2
  34512 3
  724533 4
  998244353 1
  12345678 10
  
  
  Output
  
  
  2021
  181111
  34533
  724542
  999999999
  12345678
solution: 
  import java.util.*;
  import java.util.Map.Entry;
  import java.lang.*;
  import java.io.*;
  import java.math.BigInteger;
  
  public class CF {
  	private static FS sc = new FS();
  	
  	private static class FS {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer("");
  		String next() {
  			while (!st.hasMoreTokens())
  				try {
  					st=new StringTokenizer(br.readLine());				               
  	            } catch (IOException e) {}
  			return st.nextToken();
  		}
  		
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  	}
  	
  	private static class extra {
  		
  		static int[] intArr(int size) {
  			int[] a = new int[size];
  			for(int i = 0; i < size; i++) a[i] = sc.nextInt();
  			return a;
  		}
  		
  		static long[] longArr(int size) {
  			long[] a = new long[size];
  			for(int i = 0; i < size; i++) a[i] = sc.nextLong();
  			return a;
  		}
  		
  		static long intSum(int[] a) {
  			long sum = 0; 
  			for(int i = 0; i < a.length; i++) {
  				sum += a[i];
  			}
  			return sum;
  		}
  		
  		static long longSum(long[] a) {
  			long sum = 0; 
  			for(int i = 0; i < a.length; i++) {
  				sum += a[i];
  			}
  			return sum;
  		}
  		
  		static LinkedList[] graphD(int vertices, int edges) {
  			LinkedList<Integer>[] temp = new LinkedList[vertices+1];
  			for(int i = 0; i <= vertices; i++) temp[i] = new LinkedList<>();
  			for(int i = 0; i < edges; i++) {
  				int x = sc.nextInt();
  				int y = sc.nextInt();
  				temp[x].add(y);
  			}
  			return temp;
  		}
  		
  		static LinkedList[] graphUD(int vertices, int edges) {
  			LinkedList<Integer>[] temp = new LinkedList[vertices+1];
  			for(int i = 0; i <= vertices; i++) temp[i] = new LinkedList<>();
  			for(int i = 0; i < edges; i++) {
  				int x = sc.nextInt();
  				int y = sc.nextInt();
  				temp[x].add(y);
  				temp[y].add(x);
  			}
  			return temp;
  		}
  		
  		static void printG(LinkedList[] temp) {
  			for(LinkedList<Integer> aa:temp) System.out.println(aa);
  		}
  		
  		static long cal(long val, long pow) {
  			if(pow == 0) return 1;
  			long res = cal(val, pow/2);
  			
  			long ret = (res*res)%mod;
  			if(pow%2 == 0) return ret;
  			return (val*ret)%mod;
  		}
  		
  		static long gcd(long a, long b) { return b == 0 ? a:gcd(b, a%b); }
  		
  	}
  	
  	static int mod = (int) 1e9 + 7;
  //	static int mod = (int) 998244353;
  	//static int max = (int) 1e6;//, sq = 316;
  	static LinkedList<Integer>[] temp;
  	static double ans;
  	
  	public static void main(String[] args) {	
  		int t = sc.nextInt();
  //		int t = 1;
  		StringBuilder ret = new StringBuilder();
  //		int k = 1;
  		while(t-- > 0) {
  			char[] ch = sc.next().toCharArray();
  			int k = sc.nextInt();
  			int[] a = new int[ch.length];
  			for(int i = 0; i < a.length; i++) a[i] = ch[i]-'0';
  			int flag = 0;
  			while(true) {
  				HashSet<Integer> s = new HashSet<>();
  				for(int c:a) s.add(c);
  //				System.out.println(s);
  				if (s.size() <= k) {
  					flag = 1;
  					break;
  				}
  				s.clear();
  				int ptr = 0;
  				for (; ; ptr++) {
  					s.add(a[ptr]);
  					if (s.size() > k) {
  						while (a[ptr] == 9) ptr--;
  						a[ptr]++;
  						for(int i = ptr + 1; i < a.length; i++) a[i] = 0;
  						break;
  					}
  				}
  			}
  			for(int aa:a) ret.append(aa);
  			ret.append("\n");
  		}
  		System.out.println(ret);
  	}
  }