package main

import (
	"bufio"
	"io"
	"math/bits"
	"os"
	"strconv"
)

const maxLen = 12

type FastScanner struct {
	data []byte
	idx  int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data}
}

func (fs *FastScanner) NextInt() int {
	n := len(fs.data)
	for fs.idx < n {
		c := fs.data[fs.idx]
		if c > ' ' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

type Info struct {
	pop         int
	mask        int
	minAny      int
	minNonZero  int
	nextGT      [10]int
	nextGTFirst [10]int
	longVal     [maxLen]int64
}

var infos [1 << 10]Info
var masksAtMost [11][]int

func sameLenMin(s string, info *Info) (int64, bool) {
	L := len(s)
	var res [maxLen]int
	for i := 0; i < L; i++ {
		cur := int(s[i] - '0')
		if info.mask&(1<<cur) != 0 {
			res[i] = cur
			continue
		}
		d := info.nextGT[cur]
		if i == 0 {
			d = info.nextGTFirst[cur]
		}
		if d != -1 {
			res[i] = d
			for j := i + 1; j < L; j++ {
				res[j] = info.minAny
			}
			var v int64
			for j := 0; j < L; j++ {
				v = v*10 + int64(res[j])
			}
			return v, true
		}
		for j := i - 1; j >= 0; j-- {
			d2 := info.nextGT[res[j]]
			if j == 0 {
				d2 = info.nextGTFirst[res[j]]
			}
			if d2 != -1 {
				res[j] = d2
				for p := j + 1; p < L; p++ {
					res[p] = info.minAny
				}
				var v int64
				for p := 0; p < L; p++ {
					v = v*10 + int64(res[p])
				}
				return v, true
			}
		}
		return 0, false
	}
	var v int64
	for i := 0; i < L; i++ {
		v = v*10 + int64(res[i])
	}
	return v, true
}

func distinctCount(s string) int {
	mask := 0
	for i := 0; i < len(s); i++ {
		mask |= 1 << int(s[i]-'0')
	}
	return bits.OnesCount(uint(mask))
}

func precompute() {
	var byPop [11][]int
	for mask := 1; mask < (1 << 10); mask++ {
		var info Info
		info.pop = bits.OnesCount(uint(mask))
		info.mask = mask
		info.minAny = 10
		info.minNonZero = 10
		for d := 0; d <= 9; d++ {
			if mask&(1<<d) != 0 {
				if d < info.minAny {
					info.minAny = d
				}
				if d > 0 && d < info.minNonZero {
					info.minNonZero = d
				}
			}
		}
		for i := 0; i < 10; i++ {
			info.nextGT[i] = -1
			info.nextGTFirst[i] = -1
			for d := i + 1; d <= 9; d++ {
				if mask&(1<<d) != 0 {
					if info.nextGT[i] == -1 {
						info.nextGT[i] = d
					}
					if d > 0 && info.nextGTFirst[i] == -1 {
						info.nextGTFirst[i] = d
					}
				}
			}
		}
		if info.minNonZero < 10 {
			v := int64(info.minNonZero)
			info.longVal[1] = v
			for l := 2; l < maxLen; l++ {
				v = v*10 + int64(info.minAny)
				info.longVal[l] = v
			}
		}
		infos[mask] = info
		byPop[info.pop] = append(byPop[info.pop], mask)
	}
	for k := 1; k <= 10; k++ {
		for p := 1; p <= k; p++ {
			masksAtMost[k] = append(masksAtMost[k], byPop[p]...)
		}
	}
}

func main() {
	precompute()
	fs := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := fs.NextInt()
	for ; t > 0; t-- {
		n := fs.NextInt()
		k := fs.NextInt()
		s := strconv.Itoa(n)

		if distinctCount(s) <= k {
			out.WriteString(s)
			out.WriteByte('\n')
			continue
		}

		best := int64(1<<62 - 1)
		L := len(s)
		for _, mask := range masksAtMost[k] {
			info := &infos[mask]
			if info.minNonZero == 10 {
				continue
			}
			if v, ok := sameLenMin(s, info); ok {
				if v < best {
					best = v
				}
			} else {
				v := info.longVal[L+1]
				if v < best {
					best = v
				}
			}
		}

		out.WriteString(strconv.FormatInt(best, 10))
		out.WriteByte('\n')
	}
}