package main

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

// MOD ...
const MOD = 2 * 3 * 5 * 7

func countUgly(scanner *bufio.Scanner) []int {
	caseCnt := ReadInt(scanner)
	answer := make([]int, caseCnt)
	for cid := 0; cid < caseCnt; cid++ {
		s := ReadLine(scanner)
		dp := make([][]int, len(s)+1)
		for i := range dp {
			dp[i] = make([]int, MOD)
		} // dp[i][j] means the count of numbers which mod MOD equals j
		dp[0][0] = 1
		for i := 0; i < len(s); i++ {
			sgn := -1
			if i == 0 {
				sgn = 1
			}
			for ; sgn <= 1; sgn += 2 {
				num := 0
				for j := i; j < len(s); j++ {
					num = (num*10 + int(s[j]-'0')) % MOD
					for x := 0; x < MOD; x++ {
						dp[j+1][(x+sgn*num+MOD)%MOD] += dp[i][x]
					}
				}
			}
		}
		for i := 0; i < MOD; i++ {
			if i%2 == 0 || i%3 == 0 || i%5 == 0 || i%7 == 0 {
				answer[cid] += dp[len(s)][i]
			}
		}
	}
	return answer
}

func main() {
	inputFiles := []string{"B-small-practice.in", "B-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := test

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := countUgly(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, v := range answer {
		s := fmt.Sprintf("Case #%d: %d\n", i+1, v)
		fout.WriteString(s)
	}
}