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.InputStreamReader;
  import java.io.PrintWriter;
  import java.util.StringTokenizer;
  
  public class lasttask {
  	public static void main(String[] args) {
  		FastScanner in = new FastScanner();
  		PrintWriter out = new PrintWriter(System.out);
  		int tt = in.nextInt();
  		for (int tc = 0; tc < tt; tc++) {
  			String s = in.next();
  			int k = in.nextInt();
  			int d[] = new int[10];
  			int map_sz = 0;
  			int p = 0;
  			StringBuilder ans = new StringBuilder(s);
  			while (p < ans.length()) {
  				d[ans.charAt(p) - '0']++;
  				if (d[ans.charAt(p) - '0'] == 1) map_sz++;
  				if (map_sz > k) {
  					break;
  				}
  				p++;
  			}
  			if (p == ans.length()) {
  				out.println(ans);
  				continue;
  			}
  			d[ans.charAt(p) - '0']--;
  			if (d[ans.charAt(p) - '0'] == 0) {
  				map_sz--;
  			}
  			while (true) {
  				if (ans.charAt(p) == '9') {
  					p--;
  					d[ans.charAt(p) - '0']--;
  					if (d[ans.charAt(p) - '0'] == 0) {
  						map_sz--;
  					}
  					continue;
  				}
  				if (map_sz < k) {
  					ans.setCharAt(p, (char) (ans.charAt(p) + 1));
  					d[ans.charAt(p) - '0']++;
  					if (d[ans.charAt(p) - '0'] == 1) map_sz++;
  					if (map_sz < k) {
  						filling(ans, '0', p + 1);
  					} else {
  						char c = '0';
  						for (int i = 0; i < 10; i++) {
  							if (d[i] > 0) {
  								c = (char) (i + '0');
  								break;
  							}
  						}
  						filling(ans, c, p + 1);
  					}
  					break;
  				}
  				int it = -1;
  				for (int i = 0; i < 10; i++) {
  					if (d[i] > 0 && i > ans.charAt(p) - '0') {
  						it = i;
  						break;
  					}
  				}
  				if (it == -1) {
  					p--;
  					d[ans.charAt(p) - '0']--;
  					if (d[ans.charAt(p) - '0'] == 0) {
  						map_sz--;
  					}
  					continue;
  				} else {
  					ans.setCharAt(p, (char) (it + '0'));
  					char c = '0';
  					for (int i = 0; i < 10; i++) {
  						if (d[i] > 0) {
  							c = (char) (i + '0');
  							break;
  						}
  					}
  					filling(ans, c, p + 1);
  					break;
  				}
  			}
  			out.println(ans);
  		}
  		out.flush();
  	}
  
  	static void filling(StringBuilder s, char c, int f) {
  		for (int i = f; i < s.length(); i++) {
  			s.setCharAt(i, c);
  		}
  	}
  
  	static class FastScanner {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer tok = new StringTokenizer("");
  		String next() {
  			while(!tok.hasMoreTokens()) {
  				try {
  					tok = new StringTokenizer(br.readLine());
  				} catch (Exception e) {
  					e.printStackTrace();
  				}
  			}
  			return tok.nextToken();
  		}
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  		float nextFloat() {
  			return Float.parseFloat(next());
  		}
  		double nextDouble() {
  			return Double.parseDouble(next());
  		}
  	}
  }
  