Exact Digit-Sum Count

**Problem.** Each line: L R K (read until EOF). Print one integer per line: the count of x in [L, R] with digit sum exactly K. **Constraints:** 1 ≤ q ≤ 20000; 1 ≤ L ≤ R ≤ 10^18; 1 ≤ K ≤ 162. Budget-state digit DP: (position, remaining budget, tight). The W drops the tight chain and undercounts every boundary.