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.*;
  import java.util.*;
  import java.text.*;
  import java.math.*;
  import java.util.regex.*;
  
  public class JaiShreeRam{
  	static Scanner in=new Scanner();
  	static long mod = 1000000007;
  	static ArrayList<ArrayList<Integer>> adj;
  	static long ans;
  	public static void main(String[] args) throws Exception{
  		int z=in.readInt();
  		while(z-->0) {
  			char[] s=in.readString().toCharArray();
  			int k=in.readInt();
  			ans=k;
  			char c[]=new char[s.length];
  			Arrays.fill(c,'0');
  			ans(0,s.length,k,c,s);
  			System.out.println(ans);
  		}
  	}
  	static boolean ans(int ind,int n,int k,char c[],char[] s) {
  		int dist=calDist(c,ind);
  		if(new String(s).substring(0,ind).compareTo(new String(c).substring(0,ind))>0)
  			return false;
  		if(ind==n) {
  			if(dist<=k) {
  				ans=Integer.parseInt(new String(c));
  				return true;
  			}
  			return false;
  		}
  		for(int j=0;j<10;j++) {
  			c[ind]+=j;
  			if(c[ind]>=s[ind]) {
  				dist=calDist(c,ind+1);
  				if(dist<=k) {
  					if(ans(ind+1,n,k,c,s))
  						return true;
  				}
  				for(int l=ind+1;l<n;l++)
  					s[l]='0';
  			}
  			c[ind]-=j;
  		}
  		return false;
  	}
  	static int calDist(char c[],int n) {
  		Set<Character> st=new HashSet<>();
  		for(int i=0;i<n;i++)
  			st.add(c[i]);
  		return st.size();
  	}
  	static int[] nextIntArray(int n){
  		int[] arr= new int[n];
  		int i=0;
  		while(i<n){
  			arr[i++]=in.readInt();
  		}
  		return arr;
  	}
  	static int[] nextIntArray1(int n){
  		int[] arr= new int[n+1];
  		int i=1;
  		while(i<=n){
  			arr[i++]=in.readInt();
  		}
  		return arr;
  	}
  	static long gcd(long a, long b) {
  		if (b==0) return a;
  		return gcd(b, a%b);
  	}
  	static class Scanner{
  		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st=new StringTokenizer("");
  		String readString() {
  			while (!st.hasMoreTokens())
  				try {
  					st=new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  			return st.nextToken();
  		}
  		double readDouble() {
  			return Double.parseDouble(readString());
  		}
  		int readInt() {
  			return Integer.parseInt(readString());
  		}
  		long readLong() {
  			return Long.parseLong(readString());
  		}
  	}	
  }