Lucky Range Count

**Description:** Given q queries, each a range [l, r] with 1 ≤ l ≤ r ≤ 10^6, count how many numbers in 1..10^6 have their digit sum between l and r (inclusive). Digit sum of 78 is 7+8 = 15. **Input:** Line 1: q (1 ≤ q ≤ 10^5). Each of the next q lines: l r. **Output:** q lines — one answer per query. **Example:** with q = 2: 1 1 → digit sum 1 happens for 1, 10, 100, ..., 10^6 has digit sum 1 → count = 7 (1, 10, 100, 1000, 10000, 100000, 1000000) → 7; 28 28 → 1 (only 99999... wait, digit sum 28: many numbers. Precompute per-value digit sums and a prefix count — do not rescan per query.)