package main

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

func main() {
	palindromes := []int{}
	for i := 1; i <= 40000; i++ {
		rev := 0
		temp := i
		for temp > 0 {
			rev = rev*10 + temp%10
			temp /= 10
		}
		if rev == i {
			palindromes = append(palindromes, i)
		}
	}

	dp := make([]int, 40005)
	dp[0] = 1
	mod := 1000000007

	for _, p := range palindromes {
		for i := p; i <= 40000; i++ {
			dp[i] = (dp[i] + dp[i-p]) % mod
		}
	}

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	
	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

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

	for i := 0; i < t; i++ {
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		fmt.Fprintln(out, dp[n])
	}
}