Exact Digit-Sum Counts

**Problem.** Each line: L R K (read until EOF). Print one integer per line: the count of x in [L, R] whose digit sum is exactly K. **Constraints:** 1 ≤ q ≤ 20000; 1 ≤ L ≤ R ≤ 10^18; 1 ≤ K ≤ 162. Per query: a 19-position walk with a digit-sum budget. The DP table is rebuilt per query — still microseconds.