I am quite new to DP. I thought of an idea to calculate nCr by DP and then calculate the number of zeroes from 0 to n and 0 to m-1. Then the answer would be zeroes(n) — zeroes(m-1). But I saw some solutions that solved this problem in totally different way of DP. I could not get the idea clear. Could you please help me out? TIA.

Problem link: LightOJ — 1140 — How Many Zeroes?

Problem Statement:

Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

Input Input starts with an integer T (≤ 11000), denoting the number of test cases.

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input

5 10 11 100 200 0 500 1234567890 2345678901 0 4294967295

Output for Sample Input Case 1: 1 Case 2: 22 Case 3: 92 Case 4: 987654304 Case 5: 3825876150