package main

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

func solveX(X int64, k int) int64 {
	if X <= 0 {
		return 0
	}

	xDigits := make([]int, 36)
	temp := X
	for i := 0; i < 36; i++ {
		xDigits[i] = int(temp % 4)
		temp /= 4
	}

	var ways [37][2][110]int64
	ways[36][0][0] = 1

	for i := 35; i >= 0; i-- {
		for isLess := 0; isLess < 2; isLess++ {
			for sum := 0; sum <= 105; sum++ {
				if ways[i+1][isLess][sum] == 0 {
					continue
				}
				limit := 3
				if isLess == 0 {
					limit = xDigits[i]
				}
				for d := 0; d <= limit; d++ {
					newIsLess := isLess
					if d < limit {
						newIsLess = 1
					}
					ways[i][newIsLess][sum+d] += ways[i+1][isLess][sum]
				}
			}
		}
	}

	var ans int64 = 0
	for c := 0; c <= 35; c++ {
		for isLess := 0; isLess < 2; isLess++ {
			for sum := 0; sum <= 105; sum++ {
				if ways[c+1][isLess][sum] == 0 {
					continue
				}
				limit := 3
				if isLess == 0 {
					limit = xDigits[c]
				}
				for d := 1; d <= limit; d++ {
					newSum := sum + d
					if newSum%3 == k%3 {
						minReq := k - 3*c
						if minReq < 1 {
							minReq = 1
						}
						if newSum >= minReq && newSum <= k {
							ans += ways[c+1][isLess][sum]
						}
					}
				}
			}
		}
	}

	return ans
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

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

	if !scanner.Scan() {
		return
	}
	t := int(0)
	for _, b := range scanner.Bytes() {
		t = t*10 + int(b-'0')
	}

	for i := 0; i < t; i++ {
		l := scanInt64()
		r := scanInt64()
		k64 := scanInt64()

		if k64 > 200 {
			fmt.Println(0)
			continue
		}
		k := int(k64)

		L := (3*l + k64 + 3) / 4
		R := (3*r + k64) / 4

		if L > R {
			fmt.Println(0)
			continue
		}

		ans := solveX(R, k) - solveX(L-1, k)
		fmt.Println(ans)
	}
}