fork(1) download
copy 
  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.         out = new PrintWriter(new BufferedOutputStream(System.out));
  194.         if(isDebug){
  195.             try {
  196.                 debug = new PrintWriter(new FileOutputStream("debug.txt"));
  197.             }catch (IOException e){
  198.                 e.printStackTrace();
  199.             }
  200.         }
  201.  
  202.     }
  203.     public static void closeIO(){
  204.         sc.close();
  205.         out.flush();
  206.         out.close();
  207.         if(debug!=null){
  208.             debug.flush();
  209.             debug.close();
  210.         }
  211.     }
  212.  
  213.     private static class Scanner {
  214.         private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  215.         private StringTokenizer st = new StringTokenizer("");
  216.  
  217.         public String next() {
  218.             while (!st.hasMoreTokens())
  219.                 try {
  220.                     st = new StringTokenizer(br.readLine());
  221.                 } catch (IOException e) {
  222.                     e.printStackTrace();
  223.                 }
  224.             return st.nextToken();
  225.  
  226.         }
  227.  
  228.         public int nextInt() {
  229.             return Integer.parseInt(next());
  230.         }
  231.  
  232.         public long nextLong() {
  233.             return Long.parseLong(next());
  234.         }
  235.  
  236.         public double nextDouble() {
  237.             return Double.parseDouble(next());
  238.         }
  239.  
  240.         public int[] set_int_array(int n) {
  241.             int[] arr = new int[n];
  242.             for (int i = 0; i < n; i++) arr[i] = nextInt();
  243.             return arr;
  244.         }
  245.  
  246.         public long[] set_long_array(int n) {
  247.             long[] arr = new long[n];
  248.             for (int i = 0; i < n; i++) arr[i] = nextLong();
  249.             return arr;
  250.         }
  251.         public double[] set_double_array(int n){
  252.             double[] arr = new double[n];
  253.             for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
  254.             return arr;
  255.         }
  256.  
  257.         public int[][] set_2D_int_array(int n) {
  258.             return set2DIntArray(n, n);
  259.         }
  260.  
  261.         public int[][] set2DIntArray(int row, int col) {
  262.             int[][] arr = new int[row][col];
  263.             for (int i = 0; i < row; i++)
  264.                 for (int j = 0; j < col; j++)
  265.                     arr[i][j] = nextInt();
  266.             return arr;
  267.         }
  268.  
  269.         public long[][] set_2D_long_array(int n) {
  270.             return set2DlongArray(n, n);
  271.         }
  272.  
  273.         public long[][] set2DlongArray(int row, int col) {
  274.             long[][] arr = new long[row][col];
  275.             for (int i = 0; i < row; i++)
  276.                 for (int j = 0; j < col; j++)
  277.                     arr[i][j] = nextLong();
  278.             return arr;
  279.         }
  280.  
  281.         public char[][] set_2D_char_array(int n) {
  282.             return set2DCharArray(n, n);
  283.         }
  284.  
  285.         public char[][] set2DCharArray(int row, int col) {
  286.             char[][] ch = new char[row][col];
  287.             for (int i = 0; i < row; i++)
  288.                 ch[i] = sc.next().toCharArray();
  289.             return ch;
  290.         }
  291.  
  292.         public void close() {
  293.             try {
  294.                 br.close();
  295.             } catch (IOException e) {
  296.                 e.printStackTrace();
  297.             }
  298.         }
  299.     }
  300.     /*****************************************FAST INPUT ENDS HERE *************************************/
  301. }
  302.  
Success #stdin #stdout 0.06s 51444KB
comments (?)
stdin
copy 
3
10 19
1 9
20 29
stdout
copy 
4
4
5
https://ideone.com/nOhUqM
problem GONE, based on SPOJ submission 28035427 (JAVA), 2021-06-10 09:14:58
language:
Java (HotSpot 12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!