// Arup Guha
// 3/12/2019
// Solution to 2019 UCF HS Contest Problem: Nate's Diverse Numbers

import java.util.*;

public class diverse {
	
	// Max value for k = 1.
	final public static long MAXONE = 9876543210L;
	
	public static String numStr;
	public static int len;
	public static long val;
	public static int k;
	public static int[] digits;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();
		
		// Process each case.
		for (int loop=0; loop<numCases; loop++) {
		
			// Redundantly store info for ease.
			numStr = stdin.next();
			len = numStr.length();
			digits = new int[len];
			for (int i=0; i<len; i++) digits[i] = numStr.charAt(i)-'0';
			val = Long.parseLong(numStr);
			k = stdin.nextInt();
			
			// Ta da!
			System.out.println(solve());
		}
	}
	
	public static String solve() {
		
		// Only case without a solution.
		if (k == 1 && val > MAXONE) return "Find a different k";
		
		// Only time our result is a different length.
		if (val > Long.parseLong(getMax(len))) return getMin(len+1);
		
		// Try fixing as many digits as possible.
		for (int i=len; i>=0; i--) {
			String tmp = fix(i);
			if (tmp != null) return tmp;
		}
		
		// Should never get here.
		return null;
	}
	
	// Returns the smallest solution with the first left digits fixed that is >= original.
	// If none exists, null is returned.
	public static String fix(int left) {
		
		int[] freq = new int[10];
		Arrays.fill(freq, k);
		
		// Check if fixed digits are illegal.
		for (int i=0; i<left; i++) {
			freq[digits[i]]--;
			if (freq[digits[i]] < 0) return null;
		}
		
		// This means the number itself is good.
		if (left == len) return numStr;
		
		// Find greatest available digit.
		int max = 0;
		for (int i=0; i<10; i++)
			if (freq[i] > 0)
				max = Math.max(max, i);
			
		// This means it's not possible, since we had already tried to fix this digit.
		if (max <= digits[left]) return null;
		
		// Find smallest available digit to put in this spot.
		int next = digits[left]+1;
		while (freq[next] == 0) next++;
		freq[next]--;
		
		// Concatenate all of the digits left from smallest to biggest.
		String res = "";
		for (int i=0; i<10; i++)
			for (int j=0; j<freq[i]; j++)
				res = res + i;
		
		// Here is our result - fixed string, plus next digit, plus minimum we can form from what's left.
		return numStr.substring(0, left) + next + res.substring(0, len-left-1);	
	}
	
	// Returns the minimum answer of length len.
	public static String getMin(int len) {
		
		// Concatenate 1 to digits in order.
		String res = "1";
		for (int i=0; i<10; i++) {
			int limit = i == 1 ? k-1 : k;
			for (int j=0; j<limit; j++)
				res = res + i;
		}
		
		// Parse out the substring we care about.
		return res.substring(0, len);
	}
	
	public static String getMax(int len) {
		
		// Just build backwards.
		String res = "";
		for (int i=9; i>=0; i--)
			for (int j=0; j<k; j++)
				res = res + i;
			
		// Cut off first len digits.
		return res.substring(0,len);
	}

}