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: // "static void main" must be defined in a public class.
  
  //System.out.println();
  // System.out.print();
  
  import java.util.*;
  import java.io.*;
  public class Main {
      
      
      static boolean isPrime(int n)
      {
          // Corner cases
          if (n <= 1) return false;
          if (n <= 3) return true;
           
          // This is checked so that we can skip
          // middle five numbers in below loop
          if (n % 2 == 0 || n % 3 == 0) return false;
           
          for (int i = 5; i * i <= n; i = i + 6)
              if (n % i == 0 || n % (i + 2) == 0)
              return false;
           
          return true;
      }
       
      // Function to return the smallest
      // prime number greater than N
      static int nextPrime(int N)
      {
       
          // Base case
          if (N <= 1)
              return 2;
       
          int prime = N;
          boolean found = false;
       
          // Loop continuously until isPrime returns
          // true for a number greater than n
          while (!found)
          {
              prime++;
       
              if (isPrime(prime))
                  found = true;
          }
       
          return prime;
      }
      
      
      public static int findXorSum(int arr[], int n)
      {
          // variable to store
          // the final sum
          long sum = 0;
       
          // multiplier
          long mul = 1;
       
          for (int i = 0; i < 30; i++)
          {
       
              // variable to store number of
              // sub-arrays with odd number of elements
              // with ith bits starting from the first
              // element to the end of the array
              long c_odd = 0;
       
              // variable to check the status
              // of the odd-even count while
              // calculating c_odd
              boolean odd = false;
       
              // loop to calculate initial
              // value of c_odd
              for (int j = 0; j < n; j++)
              {
                  if ((arr[j] & (1 << i)) > 0)
                      odd = (!odd);
                  if (odd)
                      c_odd++;
              }
       
              // loop to iterate through
              // all the elements of the
              // array and update sum
              for (int j = 0; j < n; j++)
              {
                  sum += (mul%1000000007 * c_odd%1000000007)%1000000007;
       
                  if ((arr[j] & (1 << i)) > 0)
                      c_odd = (n - j - c_odd);
              }
       
              // updating the multiplier
              mul = (mul%1000000007 * 2)%1000000007;
          }
       
          // returning the sum
          return (int)sum;
      }
      
      
      public static long fact(long n)
      {
          return (n == 1 || n == 0) ? 1 : n * fact(n - 1);
      }
      
      public static long nCr(long n, long r){
          return fact(n) / (fact(r) * fact(n - r));
      }
      
      public static long nPr(long n, long r){
          return fact(n) / fact(n - r);
      }
      
      public static long gcd(long a , long b){
          if(b==0){
              return a;
          }
          return gcd(b,a%b);
      }
      
      public static long lcm(long a, long b){return (a*b)/gcd(a,b);}
      
      public static long fPow(long x, long y, long p){
          long res = 1; // Initialize result
  
          x = x % p; // Update x if it is more than or
          // equal to p
  
          if (x == 0)
            return 0; // In case x is divisible by p;
  
          while (y > 0)
          {
  
            // If y is odd, multiply x with result
            if ((y & 1) != 0)
              res = (res * x) % p;
  
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
          }
          return res;
      }
      
      public static int binS(int[] sortedArray, int key, int low, int high) {
      int index = Integer.MAX_VALUE;
      
      while (low <= high) {
          int mid = low  + ((high - low) / 2);
          if (sortedArray[mid] < key) {
              low = mid + 1;
          } else if (sortedArray[mid] >= key) {
              high = mid - 1;
          }
          // else if (sortedArray[mid] == key) {
          //     low = mid;
          //     break;
          // }
      }
      return low;
  }
      
      public static int binS1(int[] sortedArray, int key, int low, int high) {
      int index = Integer.MAX_VALUE;
      
      while (low <= high) {
          int mid = low  + ((high - low) / 2);
          if (sortedArray[mid] <= key) {
              low = mid + 1;
          } else if (sortedArray[mid] > key) {
              high = mid - 1;
          }
          // else if (sortedArray[mid] == key) {
          //     low = mid;
          //     break;
          // }
      }
      return high;
  }
          
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int t = Integer.parseInt(br.readLine());
          for(int q=0;q<t;q++){
              // int n = Integer.parseInt(br.readLine());
              String s1[] = br.readLine().split(" ");
              // int n = Integer.parseInt(s[0]);
              String s = s1[0];
              int k = Integer.parseInt(s1[1]);
              // int c = Integer.parseInt(s[2]);
              // String s1[] = br.readLine().split(" ");
              // int a[] = new int[n];
              // for(int i=0;i<n;i++){
              //     a[i] = Integer.parseInt(s1[i]);
              // }
              HashMap<Integer,Integer> hm = new HashMap<>();
              int n = s.length();
              int min=Integer.MAX_VALUE;
              for(int i=0;i<n;i++){
                  int num = (int)s.charAt(i)-48;
                  
                  // System.out.println(num);
                  if(hm.containsKey(num)){
                      hm.replace(num,hm.get(num)+1);
                  }
                  else if(!hm.containsKey(num) && hm.size()<k){
                      hm.put(num,1);
                  }
                  else{
                      int num1 = (int)s.charAt(i-1)-48;
                      if(num<num1){
                          int tmp1=0;
                          for(int ii=0;ii<10;ii++){
                              if(hm.containsKey(ii)){
                                  num1=ii;
                                  break;
                              }
                          }
                          int last=0;
                          for(int ii=num;ii<10;ii++){
                              if(hm.containsKey(ii)){
                                  last=ii;
                                  break;
                              }
                          }
                          // if(hm.containsKey(last)){
                          //         num1=0;
                          //     }
                          if(min>last){
                              min=last;
                          }
                          String str = (last)+"";
                          for(int ii=0;ii<(n-i-1);ii++){
                              str = str.concat(num1+"");
                          }
                          s = s.substring(0,i)+str;
                          break;
                      }
                      else{
                          int ind=i-1;
                          int big = -1;
                          int num11=-1;
                          for(int ii=0;ii<10;ii++){
                              if(hm.containsKey(ii)){
                                  num11=ii;
                                  break;
                              }
                          }
                          min = num11;
                          
                          for(int ii=num;ii<10;ii++){
                              if(hm.containsKey(ii)){
                                  big=ii;
                                  break;
                              }
                          }
                          if(min>big){
                              min=big;
                          }
                          
                          // System.out.println(big);
                          if(big==-1){
                              int temp=-2;
                          while(hm.size()>=k){
                              int num2 = (int)s.charAt(ind)-48;
                              hm.replace(num2,hm.get(num2)-1);
                              if(hm.get(num2)==0){
                                  temp=num2;
                                  hm.remove(num2);
                              }
                              if(temp==-2){
                              for(int ii=num2+1;ii<10;ii++){
                              if(hm.containsKey(ii)){
                                  big=ii;
                                  break;
                              }
                          }
                              if(big!=-1){
                                  ind--;
                                  hm.remove(big);
                                  break;
                              }
                              }
                              ind--;
                          }
                              
                           if(temp!=-2)
                           big = temp+1;
                              min=big;
                              for(int ii=0;ii<10;ii++){
                              if(hm.containsKey(ii) && min>ii){
                                  min=ii;
                                  break;
                              }
                          }
                              if(hm.containsKey(big)){
                                  min=0;
                              }
                          }
                          
                          ind++;
                          String str = big+"";
                          for(int ii=0;ii<(n-ind-1);ii++){
                              str = str.concat(min+"");
                          }
                          s = s.substring(0,ind)+str;
                          // System.out.println(s);
                          break;
                      }
                  }
              }
              System.out.println(s);
          }
      }
  }
  //1116776899 3