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.math.*;
  import java.io.*;
  
  public class Main {
  	public static void main(String[] args) throws FileNotFoundException {
  		InputReader in = new InputReader(System.in);
  		// Scanner in = new Scanner(System.in);
  		// Scanner in = new Scanner(new BufferedReader(new
  		// InputStreamReader(System.in)));
  		PrintWriter out = new PrintWriter(System.out);
  		// InputReader in = new InputReader(new
  		// File("ethan_traverses_a_tree.txt"));
  		// PrintWriter out = new PrintWriter(new
  		// File("ethan_traverses_a_tree-output.txt"));
  
  		int pi = in.nextInt();
  		for (int qi = 0; qi < pi; qi++) {
  			long n = in.nextLong();
  			int k = in.nextInt();
  
  			int m = getnsize(n);
  			int[] a = new int[m];
  			Set<Integer> set = new HashSet<Integer>();
  
  			for (int i = 0; i < m; i++) {
  				for (int j = 0; j < 10; j++) {
  					if (set.size() < k || set.contains(j) == true) {
  						a[i] = j;
  						if (getmax(a, k, i) >= n) {
  							break;
  						}
  					}
  				}
  
  				set.add(a[i]);
  			}
  
  			long ans = getn(a);
  			out.printf("%d\n", ans);
  		}
  
  		out.close();
  	}
  
  	public static int getnsize(long k) {
  		int count = 0;
  		while (k != 0) {
  			k = k / 10;
  			count++;
  		}
  		return count;
  	}
  
  	public static long getmax(int[] tmpa, int k, int fixm) {
  		int m = tmpa.length;
  		int[] a = new int[m];
  		for (int i = 0; i < m; i++) {
  			a[i] = tmpa[i];
  		}
  
  		Set<Integer> set = new HashSet<Integer>();
  
  		int maxdigit = 0;
  		for (int i = 0; i <= fixm; i++) {
  			set.add(a[i]);
  			maxdigit = Math.max(maxdigit, a[i]);
  		}
  
  		if (set.size() == k) {
  			for (int i = fixm + 1; i < m; i++) {
  				a[i] = maxdigit;
  			}
  		} else {
  			for (int i = fixm + 1; i < m; i++) {
  				a[i] = 9;
  			}
  		}
  
  		return getn(a);
  	}
  
  	public static long getn(int[] a) {
  		int m = a.length;
  		long res = 0;
  
  		for (int i = 0; i < m; i++) {
  			res = res * 10 + a[i];
  		}
  
  		return res;
  	}
  
  	static class InputReader {
  		BufferedReader br;
  		StringTokenizer st;
  
  		public InputReader(File f) {
  			try {
  				br = new BufferedReader(new FileReader(f));
  			} catch (FileNotFoundException e) {
  				e.printStackTrace();
  			}
  		}
  
  		public InputReader(InputStream in) {
  			br = new BufferedReader(new InputStreamReader(in));
  		}
  
  		public String next() {
  			while (st == null || !st.hasMoreTokens()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
  
  		public boolean hasNext() {
  			while (st == null || !st.hasMoreTokens()) {
  				String s = null;
  				try {
  					s = br.readLine();
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  				if (s == null)
  					return false;
  				st = new StringTokenizer(s);
  			}
  			return true;
  		}
  
  		public int nextInt() {
  			return Integer.parseInt(next());
  		}
  
  		public long nextLong() {
  			return Long.parseLong(next());
  		}
  
  		public double nextDouble() {
  			return Double.parseDouble(next());
  		}
  	}
  }