Recycled Numbers

Time Limit:2000MS  Memory Limit:65535KB
Description:
Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?

Input:
The first line of the input gives the number of test cases, TT test cases follow. Each test case consists of a single line containing the integers and B.

Limits

1 ≤ T ≤ 50.
1 ≤ A ≤ B ≤ 2000000.
A and B have the same number of digits.

Output:
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with A ≤ n < m ≤ B.
Sample test:
Input
4
1 9
10 40
100 500
1111 2222
Output
Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287
Note:

Are we sure about the output to Case #4?   Yes, we're sure about the output to Case #4.

Many contestants got stuck in this problem because of the sample test case number 4. Let's say n is 1212, then after moving 1 or 3 digits you will get 2121, hence the pair (1212, 2121) will be counted twice if you count all possible moves. You can avoid this by breaking out of the loop once you reach the original number again, which will happen after moving 2 digits in the above example.

Source:
Google code jam Qualification Round 2012 Problem C
Author:
ACSolo