fork download
  1. /*
  2.   created by: nitin23329
  3.   on Date: 09/06/21
  4. */
  5. import java.io.*;
  6. import java.util.*;
  7. /*****************************************WRITING CODE STARTS HERE******************************************/
  8. class CodeForces {
  9.  
  10. static long [][][] dp = new long[18][140][2];
  11. private static void solve() {
  12. long l = sc.nextLong();
  13. long r = sc.nextLong();
  14. long ans = 0;
  15. if(r>0)ans += helper(r);
  16. if(l-1>0) ans -= helper(l-1);
  17. out.println(ans);
  18. }
  19. private static long helper(long n){
  20. int digitLength = countDigitBase10(n);
  21. int[] digitArray = new int[digitLength];
  22. for(int i = digitLength-1;i>=0;i--){
  23. digitArray[i] = (int)(n % 10);
  24. n/=10;
  25. }
  26. for(int i=0;i<dp.length;i++)
  27. for(int j=0;j<dp[0].length;j++)
  28. dp[i][j] = new long[]{-1,-1};
  29.  
  30. return memo(0,0,1,digitArray);
  31.  
  32. }
  33. private static long memo(int i,int currDigitSum,int isBounded,int[] digitArray){
  34. if(i==digitArray.length)return currDigitSum;
  35. if(dp[i][currDigitSum][isBounded]!=-1)return dp[i][currDigitSum][isBounded];
  36. long ans = 0;
  37. if(isBounded==1){
  38. for(int digit = 0;digit <= digitArray[i];digit++){
  39. ans += memo(i+1,currDigitSum + digit,digit == digitArray[i]?1:0,digitArray);
  40. }
  41. }else {
  42. for(int digit = 0;digit <= 9;digit++){
  43. ans += memo(i+1,currDigitSum + digit,0,digitArray);
  44. }
  45. }
  46. return dp[i][currDigitSum][isBounded] = ans;
  47. }
  48.  
  49. /*****************************************WRITING CODE ENDS HERE******************************************/
  50.  
  51. public static void main(String[] args){
  52. FIO(false);
  53. int testCase = 1;
  54. testCase = sc.nextInt();
  55. while (testCase-- > 0) solve();
  56. closeIO();
  57. }
  58.  
  59. static Scanner sc ; // FAST INPUT
  60. static PrintWriter out; // FAST OUTPUT
  61. static PrintWriter debug ; // DEBUG IN FILE : debug.txt
  62.  
  63.  
  64. /**************************************HELPER FUNCTION STARTS HERE ************************************/
  65.  
  66. public static int mod = (int) 1e9 + 7;
  67. public static final int INT_MAX = Integer.MAX_VALUE;
  68. public static final int INT_MIN = Integer.MIN_VALUE;
  69. public static final long LONG_MAX = Long.MAX_VALUE;
  70. public static final long LONG_MIN = Long.MIN_VALUE;
  71. public static final double DOUBLE_MAX = Double.MAX_VALUE;
  72. public static final double DOUBLE_MIN = Double.MIN_VALUE;
  73. public static final String YES = "YES";
  74. public static final String NO = "NO";
  75.  
  76. public static void sort(int[] a, boolean isAscending) {
  77. ArrayList<Integer> temp = new ArrayList<>();
  78. for (int j : a) temp.add(j);
  79. sort(temp, isAscending);
  80. for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  81. }
  82.  
  83. public static void sort(long[] a, boolean isAscending) {
  84. ArrayList<Long> temp = new ArrayList<>();
  85. for (long ele : a) temp.add(ele);
  86. sort(temp, isAscending);
  87. for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  88. }
  89.  
  90. public static void sort(List list, boolean isAscending) {
  91. if (isAscending)
  92. Collections.sort(list);
  93. else Collections.sort(list, Collections.reverseOrder());
  94. }
  95. // count the length of a number, time O(1)
  96. public static int countDigitBase10(long n){
  97. if(n == 0) return 0;
  98. return (int)(1 + Math.log10(n));
  99. }
  100.  
  101. // euclidean algorithm
  102. public static long gcd(long a, long b) {
  103. // time O(max (loga ,logb))
  104. long x = Math.min(a, b);
  105. long y = Math.max(a, b);
  106. if (y % x == 0) return x;
  107. return gcd(y % x, x);
  108. }
  109.  
  110. public static long lcm(long a, long b) {
  111. // lcm(a,b) * gcd(a,b) = a * b
  112. return (a / gcd(a, b)) * b;
  113. }
  114.  
  115. public static long power(long x, long n) {
  116. // time O(logn)
  117. long ans = 1;
  118. while (n > 0) {
  119. if ((n & 1) == 1) {
  120. ans *= x;
  121. ans %= mod;
  122. n--;
  123. } else {
  124. x *= x;
  125. x %= mod;
  126. n >>= 1;
  127. }
  128. }
  129. return ans;
  130. }
  131.  
  132. public static long factorial(long n) {
  133. long fact = 1L;
  134. for (int i = 2; i <= n; i++) fact = (fact * i) % mod;
  135. return fact;
  136. }
  137.  
  138. public static long firstDivisor(long n) {
  139. if (n == 1 || n == 0) return n;
  140. for (long i = 2; i * i <= n; i++)
  141. if (n % i == 0) return i;
  142. return -1;
  143. }
  144.  
  145. public static int ncr(int n, int r) {
  146. // time O(n+r)
  147. if (r > n)
  148. return 0;
  149. long[] inv = new long[r + 1];
  150. inv[1] = 1;
  151. // Getting the modular inversion
  152. // for all the numbers
  153. // from 2 to r with respect to m
  154. for (int i = 2; i <= r; i++) {
  155. inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  156. }
  157. int ans = 1;
  158. // for 1/(r!) part
  159. for (int i = 2; i <= r; i++) {
  160. ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);
  161. }
  162. // for (n)*(n-1)*(n-2)*...*(n-r+1) part
  163. for (int i = n; i >= (n - r + 1); i--) {
  164. ans = (int) (((ans % mod) * (i % mod)) % mod);
  165. }
  166. return ans;
  167. }
  168.  
  169. public static long max3(long a, long b, long c) { return max2(max2(a, b), c);}
  170.  
  171. public static long max2(long a, long b) {return Math.max(a, b);}
  172.  
  173. public static long min3(long a, long b, long c) {return min2(min2(a, b), c);}
  174.  
  175. public static long min2(long a, long b) { return Math.min(a, b); }
  176.  
  177. public static int max3(int a, int b, int c) { return max2(max2(a, b), c); }
  178.  
  179. public static int max2(int a, int b) { return Math.max(a, b); }
  180.  
  181. public static int min3(int a, int b, int c) { return min2(min2(a, b), c); }
  182.  
  183. public static int min2(int a, int b) {
  184. return Math.min(a, b);
  185. }
  186.  
  187. /**************************************HELPER FUNCTION ENDS HERE ************************************/
  188.  
  189. /*****************************************FAST INPUT STARTS HERE *************************************/
  190.  
  191. public static void FIO(boolean isDebug){
  192. sc = new Scanner();
  193. if(isDebug){
  194. try {
  195. debug = new PrintWriter(new FileOutputStream("debug.txt"));
  196. }catch (IOException e){
  197. e.printStackTrace();
  198. }
  199. }
  200.  
  201. }
  202. public static void closeIO(){
  203. sc.close();
  204. out.flush();
  205. out.close();
  206. if(debug!=null){
  207. debug.flush();
  208. debug.close();
  209. }
  210. }
  211.  
  212. private static class Scanner {
  213. private StringTokenizer st = new StringTokenizer("");
  214.  
  215. public String next() {
  216. while (!st.hasMoreTokens())
  217. try {
  218. st = new StringTokenizer(br.readLine());
  219. } catch (IOException e) {
  220. e.printStackTrace();
  221. }
  222. return st.nextToken();
  223.  
  224. }
  225.  
  226. public int nextInt() {
  227. return Integer.parseInt(next());
  228. }
  229.  
  230. public long nextLong() {
  231. return Long.parseLong(next());
  232. }
  233.  
  234. public double nextDouble() {
  235. return Double.parseDouble(next());
  236. }
  237.  
  238. public int[] set_int_array(int n) {
  239. int[] arr = new int[n];
  240. for (int i = 0; i < n; i++) arr[i] = nextInt();
  241. return arr;
  242. }
  243.  
  244. public long[] set_long_array(int n) {
  245. long[] arr = new long[n];
  246. for (int i = 0; i < n; i++) arr[i] = nextLong();
  247. return arr;
  248. }
  249. public double[] set_double_array(int n){
  250. double[] arr = new double[n];
  251. for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
  252. return arr;
  253. }
  254.  
  255. public int[][] set_2D_int_array(int n) {
  256. return set2DIntArray(n, n);
  257. }
  258.  
  259. public int[][] set2DIntArray(int row, int col) {
  260. int[][] arr = new int[row][col];
  261. for (int i = 0; i < row; i++)
  262. for (int j = 0; j < col; j++)
  263. arr[i][j] = nextInt();
  264. return arr;
  265. }
  266.  
  267. public long[][] set_2D_long_array(int n) {
  268. return set2DlongArray(n, n);
  269. }
  270.  
  271. public long[][] set2DlongArray(int row, int col) {
  272. long[][] arr = new long[row][col];
  273. for (int i = 0; i < row; i++)
  274. for (int j = 0; j < col; j++)
  275. arr[i][j] = nextLong();
  276. return arr;
  277. }
  278.  
  279. public char[][] set_2D_char_array(int n) {
  280. return set2DCharArray(n, n);
  281. }
  282.  
  283. public char[][] set2DCharArray(int row, int col) {
  284. char[][] ch = new char[row][col];
  285. for (int i = 0; i < row; i++)
  286. ch[i] = sc.next().toCharArray();
  287. return ch;
  288. }
  289.  
  290. public void close() {
  291. try {
  292. br.close();
  293. } catch (IOException e) {
  294. e.printStackTrace();
  295. }
  296. }
  297. }
  298. /*****************************************FAST INPUT ENDS HERE *************************************/
  299. }
Success #stdin #stdout 0.07s 51608KB
stdin
3
0 10
28 31
1234 56789
stdout
46
28
1128600