fork download
  1. /*
  2.   created by: nitin23329
  3.   on Date: 09/06/21
  4. */
  5.  
  6. import java.io.*;
  7. import java.util.*;
  8. /*****************************************WRITING CODE STARTS HERE******************************************/
  9. class CodeForces {
  10.  
  11. private static void solve() {
  12. int l = sc.nextInt();
  13. int r = sc.nextInt();
  14. int[][][] dp1 = new int[10][90][2];
  15. int[][][] dp2 = new int[10][90][2];
  16. for(int i=0;i<dp1.length;i++)
  17. for(int j=0;j<dp1[0].length;j++){
  18. dp1[i][j] = new int[]{-1,-1};
  19. dp2[i][j] = new int[]{-1,-1};
  20. }
  21.  
  22. int ans = digitDP(0,0,0,findDigitArray(r),dp1) - (l>1?digitDP(0,0,0,findDigitArray(l-1),dp2):0);
  23. out.println(ans);
  24. }
  25. private static int digitDP(int i,int sum,int isBounded,int[] digitsOfR,int[][][] dp){
  26. if(i==digitsOfR.length)
  27. return firstDivisor(sum) == -1 ?1:0;
  28. if(dp[i][sum][isBounded]!=-1)return dp[i][sum][isBounded];
  29. int ans = 0;
  30. if(isBounded==1 || i == 0){
  31. for(int digit = 0;digit <= digitsOfR[i];digit++)
  32. ans += digitDP(i+1,sum + digit,digit == digitsOfR[i]?1:0,digitsOfR,dp);
  33. }
  34. else {
  35. for(int digit = 0; digit <= 9; digit++)
  36. ans += digitDP(i+1,sum + digit,0,digitsOfR,dp);
  37. }
  38. return dp[i][sum][isBounded] = ans;
  39. }
  40. private static int[] findDigitArray(int n){
  41. int len = countDigitBase10(n);
  42. int[] digitArray = new int[len];
  43. for(int i = len-1;i>=0;i--){
  44. digitArray[i] = n%10;
  45. n/=10;
  46. }
  47. return digitArray;
  48. }
  49.  
  50. /*****************************************WRITING CODE ENDS HERE******************************************/
  51.  
  52. public static void main(String[] args){
  53. FIO(false);
  54. int testCase = 1;
  55. testCase = sc.nextInt();
  56. while (testCase-- > 0) solve();
  57. closeIO();
  58. }
  59.  
  60. static Scanner sc ; // FAST INPUT
  61. static PrintWriter out; // FAST OUTPUT
  62. static PrintWriter debug ; // DEBUG IN FILE : debug.txt
  63.  
  64.  
  65. /**************************************HELPER FUNCTION STARTS HERE ************************************/
  66.  
  67. public static int mod = (int) 1e9 + 7;
  68. public static final int INT_MAX = Integer.MAX_VALUE;
  69. public static final int INT_MIN = Integer.MIN_VALUE;
  70. public static final long LONG_MAX = Long.MAX_VALUE;
  71. public static final long LONG_MIN = Long.MIN_VALUE;
  72. public static final double DOUBLE_MAX = Double.MAX_VALUE;
  73. public static final double DOUBLE_MIN = Double.MIN_VALUE;
  74. public static final String YES = "YES";
  75. public static final String NO = "NO";
  76.  
  77. public static void sort(int[] a, boolean isAscending) {
  78. ArrayList<Integer> temp = new ArrayList<>();
  79. for (int j : a) temp.add(j);
  80. sort(temp, isAscending);
  81. for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  82. }
  83.  
  84. public static void sort(long[] a, boolean isAscending) {
  85. ArrayList<Long> temp = new ArrayList<>();
  86. for (long ele : a) temp.add(ele);
  87. sort(temp, isAscending);
  88. for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  89. }
  90.  
  91. public static void sort(List list, boolean isAscending) {
  92. if (isAscending)
  93. Collections.sort(list);
  94. else Collections.sort(list, Collections.reverseOrder());
  95. }
  96. // count the length of a number, time O(1)
  97. public static int countDigitBase10(long n){
  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. }
  300.  
Success #stdin #stdout 0.06s 51444KB
stdin
3
10 19
1 9
20 29
stdout
4
4
5