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.io.BufferedReader;
  import java.io.BufferedWriter;
  import java.io.FileNotFoundException;
  import java.io.FileReader;
  import java.io.FileWriter;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.io.PrintWriter;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashSet;
  import java.util.StringTokenizer;
  
  public class CF1560F1_NearestBeautifulNumberEasy {
  	static class IO {
  		private boolean type;
  		private BufferedReader br;
  		private StringTokenizer st;
  		private PrintWriter pw;
  
  		public IO() {
  			br = new BufferedReader(new InputStreamReader(System.in));
  			type = false;
  		}
  
  		public IO(String file) {
  			type = true;
  			try {
  				br = new BufferedReader(new FileReader(file + ".in"));
  				pw = new PrintWriter(new BufferedWriter(new FileWriter(file + ".out")));
  			} catch (FileNotFoundException e) {
  				e.printStackTrace();
  			} catch (IOException e) {
  				e.printStackTrace();
  			}
  		}
  
  		String next() {
  			while (st == null || !st.hasMoreElements()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
  
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  
  		double nextDouble() {
  			return Double.parseDouble(next());
  		}
  
  		String nextLine() {
  			String str = "";
  			try {
  				str = br.readLine();
  			} catch (IOException e) {
  				e.printStackTrace();
  			}
  			return str;
  		}
  
  		void print(Object b) {
  			if (type)
  				pw.print(b);
  			else
  				System.out.print(b);
  		}
  
  		void println(Object b) {
  			if (type)
  				pw.println(b);
  			else
  				System.out.println(b);
  		}
  
  		void println() {
  			if (type)
  				pw.println();
  			else
  				System.out.println();
  		}
  
  		void close() {
  			if (type)
  				try {
  					br.close();
  					pw.close();
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  		}
  
  		void fill(int[] arr) {
  			for (int i = 0; i < arr.length; i++) {
  				arr[i] = nextInt();
  			}
  		}
  
  		void fill(int[] arr, int add) {
  			for (int i = 0; i < arr.length; i++) {
  				arr[i] = nextInt() + add;
  			}
  		}
  
  		void fill(int[][] arr) {
  			for (int[] a : arr)
  				fill(a);
  		}
  
  	}
  
  	static int[] pow = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
  
  	public static void main(String[] args) {
  		// TODO Auto-generated method stub
  		IO io = new IO();
  		int te = io.nextInt();
  		for (int t = 0; t < te; t++) {
  			char[] num = io.next().toCharArray();
  			int k = io.nextInt();
  			while (true) {
  				HashSet<Character> start = new HashSet<Character>();
  				HashSet<Character> hs = new HashSet<Character>();
  				for (int i = 0; i < num.length; i++)
  					start.add(num[i]);
  				if (start.size() <= k) {
  					io.println(String.valueOf(num));
  					break;
  				}
  
  				for (int i = 0; i < num.length; i++) {
  					hs.add(num[i]);
  					if (hs.size() > k) {
  						while (num[i] == '9')
  							i--;
  						
  						num[i]++;
  						for (int j = i + 1; j < num.length; j++)
  							num[j] = '0';
  						break;
  					}
  				}
  			}
  			
  		}
  
  //			int[] count = new int[10];
  //			int[] first = new int[10];
  //			Arrays.fill(first, -1);
  //			int cnt = 0;
  //
  //			int start = -1;
  //			for (int i = 0; i < num.length; i++) {
  //				int j = num[i] - 48;
  //				if (count[j] == 0) {
  //					cnt++;
  //				}
  //
  //				if (cnt > k) {
  //					start = i;
  //					break;
  //				} else {
  //					first[j] = i;
  //					count[j]++;
  //				}
  //			}
  //			if (start == -1) {
  //				io.println(n);
  //				continue;
  //			}
  //
  //			int maxright = -1;
  //			for (int i = start; i < num.length; i++) {
  //				maxright = Math.max(maxright, num[i] - 48);
  //			}
  //
  //			int minleft = Integer.MAX_VALUE;
  //			int last = -1;
  //			for (int i = 0; i < 10; i++) {
  //				if (first[i] > -1) {
  //					last = Math.max(last, first[i]);
  //					minleft = Math.min(minleft, i);
  //				}
  //			}
  //			int front = -1;
  //
  //			if (first[(num[last] - 48 + 1) % 10] != -1) {
  //				num[last]++;
  //				if (num[last] == 10) {
  //					num[last] = 0;
  //					if (last == 0) {
  //						front = 1;
  //					}
  //				}
  //				for (int i = last + 1; i < num.length; i++)
  //					num[i] = '0';
  //			} else {
  //				num[last]++;
  //				for (int i = last + 1; i < num.length; i++) {
  //					num[i] = (char) (minleft + 48);
  //				}
  //			}
  //			
  //			if(front != -1)
  //				io.print(front);
  //			
  //			for(int i = 0; i< num.length; i++) {
  //				io.print(num[i]);
  //			}
  //			io.println();
  
  //			int n = io.nextInt();
  //			char[] num = String.valueOf(n).toCharArray();
  //			int k = io.nextInt();
  //
  //			int[] count = new int[10];
  //			int[] first = new int[10];
  //			Arrays.fill(first, -1);
  //			int cnt = 0;
  //
  //			int start = -1;
  //			for (int i = 0; i < num.length; i++) {
  //				int j = num[i] - 48;
  //				if (count[j] == 0) {
  //					first[j] = i;
  //					cnt++;
  //				}
  //				count[j]++;
  //				if (cnt > k) {
  //					start = i;
  //					break;
  //				}
  //			}
  //			if (start == -1) { io.println(n); continue; }
  //			
  //			int max = Integer.MIN_VALUE;
  //			for(int i = start; i < num.length; i++) {
  //				max = Math.max(max, num[i] - 48);
  //			}
  //			
  //			int min = -1;
  //			for(int i = 0; i < 10; i++) {
  //				if(i >= max && first[i] > min) min = first[i];
  //			}
  //			
  //			int s;
  //			if (min != -1)
  //				s = num[min] - 48;
  //			else
  //				s = max;
  //			
  
  //			if(num == 1000000000) {
  //				io.println(k == 1 ? "1111111111" : "1000000000");
  //				continue;
  //			}
  //			int[] count = new int[10];
  //			for(int i = 0; i < n.length; i++) {
  //				count[n[i]-48]++;
  //			}
  //			if(k == 1) {
  //				
  //				int diff = 0;
  //				for(int i = 0 ; i < 10; i++) {
  //					if(count[i] > 0)
  //						diff++;
  //				}
  //				if(diff == 1) {
  //					io.println(num);
  //					continue;
  //				}
  //				int[] ansarr = new int[n.length];
  //				long ans = 0;
  //				for(int i = 0; i < n.length; i++) {
  //					ansarr[i] = (int)n[0]-48;
  //					ans+= pow[n.length-i-1] * ansarr[i]; // check
  //				}
  //				if(ans < num) {
  //					ans = 0;
  //					for(int i = 0; i < n.length; i++) {
  //						ansarr[i]++;
  //						ans+= pow[n.length-i-1] * ansarr[i]; // check
  //
  //					}
  //					io.println(ans);
  //					continue;
  //				} 
  //				io.println(ans);
  //				continue;
  //			} else {
  //				int diff = 0;
  //				for(int i = 0 ; i < 10; i++) {
  //					if(count[i] > 0)
  //						diff++;
  //				}
  //				if(diff <= 2) {
  //					io.println(num);
  //					continue;
  //				}
  //				int[] ansarr = new int[n.length];
  //				long ans = 0;
  //				for(int i = n.length; i < 10; i++) {
  //					for(int )
  //				}
  //				if(ans < num) {
  //					ans = 0;
  //					for(int i = 0; i < n.length; i++) {
  //						ansarr[i]++;
  //						ans+= pow[n.length-i-1] * ansarr[i]; // check
  //
  //					}
  //					io.println(ans);
  //					continue;
  //				} 
  //				io.println(ans);
  //				continue;
  //			}
  //		}
  		
  	}
  
  }
  