```go
package main

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

func g(N uint64, M int, limit int) uint64 {
	k := M / 4
	b := M % 4

	c_k := uint64(0)
	for d := 0; d <= limit; d++ {
		if ((d >> b) & 1) == 1 {
			c_k++
		}
	}

	var ans uint64 = 0
	prefix_valid := true

	for p := 14; p >= 0; p-- {
		if !prefix_valid {
			break
		}

		Rp := int((N >> (p * 4)) & 15)

		valid_d := uint64(0)
		max_d := Rp - 1
		if limit < max_d {
			max_d = limit
		}
		for d := 0; d <= max_d; d++ {
			if p == k {
				if ((d >> b) & 1) == 0 {
					continue
				}
			}
			valid_d++
		}

		if valid_d > 0 {
			ways := uint64(1)
			if p > k {
				ways = c_k
				for i := 0; i < p-1; i++ {
					ways *= uint64(limit + 1)
				}
			} else {
				for i := 0; i < p; i++ {
					ways *= uint64(limit + 1)
				}
			}
			ans += valid_d * ways
		}

		if Rp > limit {
			prefix_valid = false
		}
		if p == k && ((Rp >> b) & 1) == 0 {
			prefix_valid = false
		}
	}

	if prefix_valid {
		ans++
	}

	return ans
}

func solve(N uint64) uint64 {
	var total uint64 = 0
	for M := 1; M <= 15; M++ {
		total += g(N, M, M) - g(N, M, M-1)
	}
	return total
}

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

	if !scanner.Scan() {
		return
	}
	q_str := scanner.Text()
	q, _ := strconv.Atoi(q_str)

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

	for i := 0; i < q; i++ {
		scanner.Scan()
		l_str := scanner.Text()
		scanner.Scan()
		r_str := scanner.Text()

		l, _ := strconv.ParseUint(l_str, 16, 64)
		r, _ := strconv.ParseUint(r_str, 16, 64)

		ans := solve(r)
		if l > 0 {
			ans -= solve(l - 1)
		}

		fmt.Fprintln(out, ans)
	}
}
```