package main

import (
	"bufio"
	"io"
	"os"
)

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) Next() (string, error) {
	// skip spaces
	for {
		b, err := fs.r.ReadByte()
		if err != nil {
			return "", err
		}
		if b > ' ' {
			buf := []byte{b}
			for {
				c, e := fs.r.ReadByte()
				if e != nil {
					if e == io.EOF {
						return string(buf), nil
					}
					return "", e
				}
				if c <= ' ' {
					return string(buf), nil
				}
				buf = append(buf, c)
			}
		}
	}
}

func parseInt(s string) int {
	sign := 1
	i := 0
	if len(s) > 0 && (s[0] == '-' || s[0] == '+') {
		if s[0] == '-' {
			sign = -1
		}
		i++
	}
	n := 0
	for ; i < len(s); i++ {
		n = n*10 + int(s[i]-'0')
	}
	return n * sign
}

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

	tsStr, err := in.Next()
	if err != nil {
		return
	}
	t := parseInt(tsStr)

	for ; t > 0; t-- {
		s, _ := in.Next()
		kStr, _ := in.Next()
		k := parseInt(kStr)

		n := len(s)
		L := n - k

		positions := [10][]int{}
		for i := 0; i < n; i++ {
			d := int(s[i] - '0')
			positions[d] = append(positions[d], i)
		}

		ptr := [10]int{}
		l := 0
		rem := L
		res := make([]byte, 0, L)

		for pick := 0; pick < L; pick++ {
			rem = L - pick
			r := n - rem
			startDigit := 0
			if pick == 0 {
				startDigit = 1
			}
			chosen := -1
			digit := 0
			for d := startDigit; d <= 9; d++ {
				list := positions[d]
				p := ptr[d]
				for p < len(list) && list[p] < l {
					p++
				}
				ptr[d] = p
				if p < len(list) && list[p] <= r {
					chosen = list[p]
					digit = d
					ptr[d] = p + 1
					break
				}
			}
			// chosen must be valid
			res = append(res, byte('0'+digit))
			l = chosen + 1
		}

		out.Write(res)
		out.WriteByte('\n')
	}
}