// Arup Guha
// 1/15/2017
// Solution to 2016 UCF HS Online Contest Problem: Sandwich

import java.util.*;

public class sandwich {

	public static long[] POW10;
	public static long[] dp;

	public static void main(String[] args) {

		// This is useful.
		POW10 = new long[13];
		POW10[0] = 1L;
		for (int i=1; i<POW10.length; i++) POW10[i] = 10*POW10[i-1];

		// dp[k] stores # of sandwich numbers of exactly k digits.
		dp = new long[12];
		dp[2] = 9;
		dp[3] = 90;
		for (int i=4; i<12; i++)
			dp[i] = solveND(i);

		// Now, process cases.
		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();
		for (int loop=1; loop<=numCases; loop++) {
			long n = stdin.nextLong();

			// 10^12 isn't a sandwich number so this hack works (avoids AOOB error).
			if (n == 1000000000000L) n = n-1;
			long res = countSandwich(n);
			System.out.println("Number #"+loop+": There are "+res+" sandwich numbers that meet our criteria.");
		}
	}

	// Returns the number of sandwich numbers <= n.
	public static long countSandwich(long n) {

		// Screen these out.
		if (n <= 10) return 0;

		int nD = numDigits(n);

		long res = 0;

		// Add in all sandwich numbers with fewer digits.
		for (int i=2; i<nD; i++)
			res += dp[i];

		// Helpful to store these prefixes.
		int[] prefixOfN = new int[nD/2+1];
		for (int i=1; i<=nD/2; i++)
			prefixOfN[i] = (int)(n/POW10[nD-i]);

		// Loop through each possible prefix.
		for (int pre=1; pre<POW10[nD/2]; pre++) {

			int preND = numDigits(pre);

			// These are too high, so we can't count all in this category.
			if (pre > prefixOfN[preND]) continue;

			// These had to have been counted.
			if (!valid(pre)) continue;

			// Add everything in this category, since these are strictly less.
			if (pre < prefixOfN[preND])
				res += numS(nD, pre);

			// Here we must add everything that fits this mold that is less or equal.
			else {

				// Middle digits in number can be anything less than midVal, so add these in.
				long midVal = strip(n, nD, preND);
				res += midVal;

				// Finally, if the prefix itself is less or equal to what's left, the middle value can be
				// matched, so we add one more.
				int left = (int)(n%POW10[preND]);
				if (pre <= left) res++;
			}
		}

		return res;
	}

	public static long solveND(int numDigits) {

		int maxDigitsPre = numDigits/2;
		long res = 0;
		for (int pre=1; pre<POW10[maxDigitsPre]; pre++) {

			// Skip over ones we've done before.
			if (!valid(pre)) continue;

			// Add these in.
			res += numS(numDigits, pre);
		}
		return res;
	}

	public static boolean valid(int prefix) {

		int nD = numDigits(prefix);

		// Check if a prefix of i digits is also a suffix of i digits.
		for (int i=1; i<nD; i++) {
			int left = (int)(prefix/POW10[nD-i]);
			int right = (int)(prefix%POW10[i]);
			if (left == right) return false;
		}

		// Ok if we get here.
		return true;
	}

	// Returns the number of digits in val.
	public static int numDigits(long val) {
		int res = 0;
		while (val > 0) {
			val /= 10;
			res++;
		}
		return res;
	}

	public static long numS(int numDigits, int prefix) {
		int numDPrefix = numDigits(prefix);
		return POW10[numDigits-2*numDPrefix];
	}

	// n must have numDigN digits, returns the value of the number obtained by stripping preND of the
	// most and least significant digits. strip(23456789, 8, 2) would return 4567.
	public static long strip(long n, int numDigN, int preND) {

		// Strip off preND least sig digits.
		n = n/POW10[preND];

		// Just take the appropriate number of least significant digits.
		return n%POW10[numDigN-2*preND];
	}
}