/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package year_2012.qualification;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * @author paul
 * @date 14 Apr 2012
 */
public class QuestionC {

    private static Set<Integer> getCycle(int x) {

        String s = Integer.toString(x);
        Set<Integer> set = new HashSet<Integer>();
        set.add(x);
        for (int c = 1; c < s.length(); c++) {
            String t = s.substring(c).concat(s.substring(0, c));
            set.add(Integer.parseInt(t));
        }
        return set;
        
    }

    private static Set<Integer> mask(Set<Integer> set, int a, int b) {
        Set<Integer> result = new HashSet<Integer>();

        for (int x : set) {
            if (x >= a && x <= b) {
                result.add(x);
            }
        }
        
        return result;

    }


    public static void main(String[] args) throws FileNotFoundException, IOException {

        String question = "C";

//        String name = "large";
        String name = "small-attempt0";
//        String name = "test";

        String filename = String.format("%s-%s", question, name);

        BufferedReader input = new BufferedReader(
                new FileReader(String.format("/home/paul/Documents/code-jam/2012/qualification/%s.in",
                filename)));

        String firstLine = input.readLine();

        PrintWriter pw = new PrintWriter(new File(
                String.format("/home/paul/Documents/code-jam/2012/qualification/%s.out", filename)));


        int T = Integer.parseInt(firstLine);

        // Loop through test cases.
        for (int i = 0; i < T; i++) {

//             Read data.
            String[] tokens = input.readLine().split(" ");

//            int N = Integer.parseInt(input.readLine());

            int A = Integer.parseInt(tokens[0]);
            int B = Integer.parseInt(tokens[1]);

//            System.out.format("%d, %d\n", A, B);

            boolean[] used = new boolean[B+1];
            int total = 0;
            for (int n = A; n <= B; n++) {
                if (!used[n]) {
                    Set<Integer> set = mask(getCycle(n), A, B);
                    int k = set.size();
                    total += (k * (k-1))/2;
                    for (int m : set) {
                        used[m] = true;
                    }
                }
            }

            pw.format("Case #%d: %d\n", i + 1, total);
        }

        pw.close();

    }

}

package qualification;

import java.util.HashMap;
import java.util.Scanner;

public class RecycledNumbers {

	//recycled numbers between A and B
	//OK, the key is being able to reduce each number to a single comparable value instead of comparing every possible match.
	//Let's say: We will take the permutation that has the smallest value.
	//creating them may be slow as long as looking them up is fast.

	//[not needed] Cache values to improve performance
	// perf test - worst possible case was solved in seconds.
	//we've only given 50 cases at most.
	//[DONE] what if more than two match? does that make 3 distinct recycled pairs?
	public static void main(final String[] args) {
		new RecycledNumbers().start();
	}

	private  void start() {
		final Scanner s = new Scanner(System.in);
		final int numTests = s.nextInt();
		for (int i = 0; i < numTests; i++) {
			//			deb("Case " + (i + 1) + "---------");
			final int startNum = s.nextInt();
			final int endNum = s.nextInt();
			final HashMap<String, Integer> values = new HashMap<String, Integer>();
			int distinctPairsCount = 0;
			for (int val = startNum; val <= endNum; val++) {
				final String newValue = findSmallestPermutation(""+val);
				if (values.containsKey(newValue)) {
					final int count = values.get(newValue);
					distinctPairsCount += count;
					values.put(newValue, count + 1);
					//					deb("found a match of " + count + ", total matches: " + distinctPairsCount);
				} else {
					values.put(newValue, 1);
				}
			}
			System.out.println("Case #" + (i+1) + ": " + distinctPairsCount);
		}
	}

	//We can't compare every permutation to every permutation
	//so we find the smallest and only use that.
	//this function looks slow, but it isn't called that often so should be OK.
	private String findSmallestPermutation(final String value) {
		int bestValue = Integer.MAX_VALUE;
		String bestString = null;
		final String valueTwice = value + value; //We will extract the substrings from this.
		for (int i = 0; i < value.length(); i++) {
			final String permutation = valueTwice.substring(i, value.length() + i);
			final int permutationValue = Integer.parseInt(permutation);
			if (permutationValue < bestValue) {
				bestValue = permutationValue;
				bestString = permutation;
			}
		}
		//		deb("source: " + value +", adding " + bestString);
		return bestString;
	}

	//	private void deb(final Object o) {
	//		System.out.println(o.toString());
	//	}

}
