package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Mask [3]uint64

func step(m Mask, d int) Mask {
	if d == 0 {
		return m
	}
	var res Mask
	res[2] = (m[2] << d) | (m[1] >> (64 - d))
	res[1] = (m[1] << d) | (m[0] >> (64 - d))
	res[0] = (m[0] << d)

	res[0] |= (m[0] >> d) | (m[1] << (64 - d))
	res[1] |= (m[1] >> d) | (m[2] << (64 - d))
	res[2] |= (m[2] >> d)

	var rev uint64
	for i := 1; i < d; i++ {
		if (m[0] & (1 << i)) != 0 {
			rev |= (1 << (d - i))
		}
	}
	res[0] |= rev
	return res
}

var states []Mask
var stateID map[Mask]int
var trans [][10]int
var layer []int

func buildAutomaton() {
	stateID = make(map[Mask]int)
	start := Mask{1, 0, 0}
	states = append(states, start)
	stateID[start] = 0
	trans = append(trans, [10]int{})
	layer = append(layer, 0)

	for i := 0; i < len(states); i++ {
		if layer[i] == 18 {
			continue
		}
		for d := 0; d < 10; d++ {
			nextM := step(states[i], d)
			id, exists := stateID[nextM]
			if !exists {
				id = len(states)
				stateID[nextM] = id
				states = append(states, nextM)
				trans = append(trans, [10]int{})
				layer = append(layer, layer[i]+1)
			}
			trans[i][d] = id
		}
	}
}

var dp [19][][10]int64

func buildDP() {
	numStates := len(states)
	for l := 0; l <= 18; l++ {
		dp[l] = make([][10]int64, numStates)
	}

	for i := 0; i < numStates; i++ {
		m := states[i]
		for k := 0; k <= 9; k++ {
			valid := false
			for x := 0; x <= k; x++ {
				if (m[0] & (1 << x)) != 0 {
					valid = true
					break
				}
			}
			if valid {
				dp[0][i][k] = 1
			}
		}
	}

	for l := 1; l <= 18; l++ {
		for i := 0; i < numStates; i++ {
			if layer[i]+l > 18 {
				continue
			}
			for d := 0; d < 10; d++ {
				nxt := trans[i][d]
				for k := 0; k <= 9; k++ {
					dp[l][i][k] += dp[l-1][nxt][k]
				}
			}
		}
	}
}

func countValid(R int64, k int) int64 {
	if R <= 0 {
		return 0
	}

	var extra int64 = 0
	if R == 1000000000000000000 {
		if k >= 1 {
			extra = 1
		}
		R--
	}

	s := strconv.FormatInt(R, 10)
	var res int64 = 0
	n := len(s)

	for l := 1; l < n; l++ {
		for d := 1; d <= 9; d++ {
			nxt := trans[0][d]
			res += dp[l-1][nxt][k]
		}
	}

	state := 0
	for i := 0; i < n; i++ {
		limit := int(s[i] - '0')
		start := 0
		if i == 0 {
			start = 1
		}

		for d := start; d < limit; d++ {
			nxt := trans[state][d]
			res += dp[n-1-i][nxt][k]
		}

		state = trans[state][limit]
	}

	m := states[state]
	valid := false
	for x := 0; x <= k; x++ {
		if (m[0] & (1 << x)) != 0 {
			valid = true
			break
		}
	}
	if valid {
		res++
	}

	return res + extra
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	return res
}

func nextInt64(scanner *bufio.Scanner) int64 {
	scanner.Scan()
	var res int64
	for _, b := range scanner.Bytes() {
		res = res*10 + int64(b-'0')
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 1024*1024*10)

	if !scanner.Scan() {
		return
	}

	nStr := scanner.Text()
	n, _ := strconv.Atoi(nStr)

	buildAutomaton()
	buildDP()

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < n; i++ {
		l := nextInt64(scanner)
		r := nextInt64(scanner)
		k := nextInt(scanner)

		ans := countValid(r, k) - countValid(l-1, k)
		fmt.Fprintln(out, ans)
	}
}