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 sys
  #py import math
  
  input = sys.stdin.readline
  
  # Läser in ett heltal 
  # n = int(input())
  
  # 3 4 5
  # Läser in tre heltal
  # x,y,z = map(int,input().split())
  
  # Läser in en lista av heltal (om man inte vet hur många)
  # a = list(map(int,input().split()))
  
  
  # Vanlig start (första raden är antal test)
  tests = int(input())
  for test in range(tests):
      tInt, k = map(int,input().split())
      t = [int(x) for x in str(tInt)]
      
      foundInts = 0
      ints = []
      firstOccurence = {}
  
      pos = 0
      
      while pos < len(t):
          char = t[pos]
          #print(char)
          if char not in ints:
              if foundInts < k:
                  ints.append(char)
                  ints.sort()
                  firstOccurence[char] = pos
                  foundInts += 1
              else:
                  break
          pos += 1
  
      if pos == len(t):
          print(''.join(str(x) for x in t))
          #print ("".join(str(t)))
      else:
          fixed = False
          #print ("slut på k")
          largerThanPos = list(filter(lambda val: val > t[pos],ints))
          #print (largerThanPos)
          if largerThanPos:
              #print ("Kan byta " + str(char) + " mot " + str(largerThanPos[0]))
              t[pos] = largerThanPos[0]
              fixed = True
          
          while not fixed:
              pos -= 1
              #print(firstOccurence)
              #print("pos: " + str(pos))
              largerThanPos = list(filter(lambda val: val > t[pos],ints))
              #print (largerThanPos)
              if firstOccurence[t[pos]] == pos:
                  #print("pos: " + str(pos))
                  ints.remove(t[pos])
                  if (t[pos]+1) in ints:
                      ints.append(0)
                      #print (ints)
                  else:
                      ints.append(t[pos]+1)
                      #print (ints)
                  t[pos] = t[pos] + 1
                  fixed = True
              elif largerThanPos:
                  #print ("Kan byta " + str(t[pos]) + " mot " + str(largerThanPos[0]))
                  t[pos] = largerThanPos[0]
                  fixed = True
              
  
          ints.sort()
          pos+=1
          while pos < len(t):
              t[pos] = ints[0]
              pos+=1
              
          print(''.join(str(x) for x in t))
  
        
                  