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.IOException;
  import java.io.InputStreamReader;
  import java.io.PrintWriter;
  import java.util.*;
  
  public class CodeForces {
      static reader input = new reader();
      static PrintWriter output = new PrintWriter(System.out);
  
      public static void main(String[] args) throws IOException {
          /*
          BufferedReader bf = new BufferedReader(new FileReader("input.txt"));
          PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
          StringTokenizer stk= new StringTokenizer(bf.readLine());;
          int n=Integer.parseInt(stk.nextToken());
          */
          F();
          output.close();
      }
  
      public static void A(){
  
      }
  
      public static void B(){
  
      }
  
      public static void C(){
  
      }
  
      public static void D(){
  
      }
  
      public static void E(){
  
      }
  
      public static void F(){
          int t=input.nextInt();
          for(int i=0;i<t;i++){
              int n=input.nextInt();
              int k=input.nextInt();
              int temp=n,digits=0;
              ArrayList<Integer>digit=new ArrayList<>();
              while(temp>0){
                  digit.add(temp%10);
                  temp/=10;
                  digits++;
              }
              Collections.reverse(digit);
              HashSet<Integer>hs=new HashSet<>();
              output.println(helper(k, 0,0,digits,true,digit,hs));
          }
      }
      public static long helper(int k,long curr,int currlen,int totallen,boolean match,ArrayList<Integer>digit,HashSet<Integer>hs){
          if(currlen==totallen)
              return curr;
          else{
              int tried=0;
              int i=currlen==0?1:0;
              for(;i<10;i++){
                  if(match&&i<digit.get(currlen)||(hs.size()==k&&!hs.contains(i)))
                      ;
                  else if(tried>=2){
                      break;
                  }
                  else{
                      tried++;
                      boolean check=hs.contains(i);
                      hs.add(i);
                      long ans=helper(k,curr*10+i,currlen+1,totallen,match&&i==digit.get(currlen),digit,hs);
                      if(!check)
                          hs.remove(i);
                      if(ans!=-1)
                          return ans;
                  }
              }
              return -1;
          }
      }
  
  
      public static long factorial(int a){
          long ans=1;
          for(int i=1;i<=a;i++){
              ans*=i;
          }
          return ans;
      }
      public static long LCM(long a,long b){
          return (a*b)/GCD(a,b);
      }
      public static long GCD(long a,long b){
          if(a==0)
              return b;
          else if(b==0)
              return a;
          else
              return GCD(b%a,a);
      }
  
      public static boolean isPrime(long num){
          if(num==1)
              return false;
          else if(num==2||num==3)
              return true;
          else if(num%2==0||num%3==0)
              return false;
          else{
              for(long i=5;i*i<=num;i+=6){
                  if(num%i==0||num%(i+2)==0)
                      return false;
              }
          }
          return true;
      }
  
      public static ArrayList<Integer> SieveofEratothenis(){
          ArrayList<Integer>ans=new ArrayList<>();
          boolean visited[]=new boolean[1000000];
          for(int i=2;i<1000000;i++){
              if(!visited[i]){
                  ans.add(i);
                  for(long j=(long)i*i;j<1000000;j+=i){
                      visited[(int)j]=true;
                  }
              }
          }
          return ans;
      }
  
      public static void mergesort(long arr[],int start,int end){//start and end must be indexes
          if(start<end) {
              int mid=(start+end)/2;
              mergesort(arr,start,mid);
              mergesort(arr, mid+1, end);
              merge(arr, start,mid,end);
          }
      }
      public static void merge(long arr[],int start,int mid,int end){
          int lsize=mid-start+1,rsize=end-mid;
          long l[]=new long[lsize],r[]=new long[rsize];
          for(int i=start;i<=mid;i++){
              l[i-start]=arr[i];
          }
          for(int i=mid+1;i<=end;i++){
              r[i-mid-1]=arr[i];
          }
          int i=0,j=0,k=start;
          while(i<lsize&&j<rsize){
              if(l[i]<=r[j]){
                  arr[k++]=l[i++];
              }else{
                  arr[k++]=r[j++];
              }
          }
          while(i<lsize)
              arr[k++]=l[i++];
          while(j<rsize)
              arr[k++]=r[j++];
      }
  }
  
  class Value{
      int ans;
      Value(int ans)
      {
          this.ans=ans;
      }
  }
  
  class Triple{
      int x,y,z;
      Triple(int x,int y,int z){
          this.x=x;
          this.y=y;
          this.z=z;
      }
  }
  
  class Pair{
      int x, y;
      Pair(int x,int y){
          this.x=x;
          this.y=y;
      }
  }
  
  class Op{
      int op,count;
      char dir;
      public Op(int op){
          this.op=op;
      }
  }
  
  class reader {
      BufferedReader br;
      StringTokenizer st;
  
      public reader() {
          br = new BufferedReader(new
                  InputStreamReader(System.in));
      }
  
      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;
      }
  
      public int[] nextIntArray(int arraySize) {
          int array[] = new int[arraySize];
          for (int i = 0; i < arraySize; i++) {
              array[i] = nextInt();
          }
          return array;
      }
  
      public long[] nextLongArray(int arraySize) {
          long array[] = new long[arraySize];
          for (int i = 0; i < arraySize; i++) {
              array[i] = nextLong();
          }
          return array;
      }
  }