A typical technique to find \(\sum_{k=L}^{R} f(k)\) is to evaluate \(\sum_{k=1}^{R} f(k) - \sum_{k=1}^{L-1} f(k)\).
This way, the original problem can be solved once \(\sum_{k=1}^{X} f(k)\) is obtained, and the implementation is simplified, so we now consider this problem instead.

While the summation itself seems hard to compute, we can rephrase it as follows. (Such a technique of counting how many times each element is counted is sometimes called “preposterous trick” in Japan.)
\(\sum_{k=1}^{X} f(k) = \) \(\sum_{k=0}^{15}\) ( The number of positive integers at most \(X\) that contains \(S\) occurring from the \(10^k\)s place )
Specifically, when \(X=234\) and \(S=\) 22, one can find \(\sum_{k=1}^{234} f(k)\) by the following steps:

• \(S\) cannot appear starting from the \(1\)s place.
• The integers within \([1,234]\) that contain \(S\) starting from the \(10\)s place are \(22,122\), and \(222\).
• The integers within \([1,234]\) that contain \(S\) starting from the \(10^2\)s place are \(220,221,222,\dots\), and \(229\).
• No integer within \([1,234]\) contains \(S\) starting from the \(10^3\)s or higher place.

Therefore, the desired sum turns out to be \(13\).

In fact, the \(i\)-th smallest integer in which \(S\) appears starting from the \(10^k\)s place can be easily found.
When \(k=3\) and \(S=\) 95, the conforming integers are in the form of ??...??95??.

• When \(i=1\), the sought integer is \(9500\).
• When \(i=13\), the sought integer is \(9512\).
• When \(i=100\), the sought integer is \(9599\).
• When \(i=101\), the sought integer is \(19500\).
• When \(i=2023\), the sought integer is \(209522\).

As you can see, the sought integer is obtained by writing \(i-1\) to the ?s (aligned at the right end).

However, extra caution is needed when \(S\) starts with 0.
When \(k=3\) and \(S=\) 05, the sought integer for \(i=1\)equals \(10500\).
To match to the explanation above, the integer to write to ?s changes to \(i-1 + 10^r\), where \(r\) is the number of ?s after \(S\).

Therefore, we can count the number of positive integers \(X\) that contains \(S\) starting from the \(10^k\)s place. All that left is to take the sum over all \(k\).
Beware of the upper bound of the binary search. When \(S\) has \(l\) letters, it is sufficient to consider up to the \(10^{16-l}\)-th one (anything later than this has at least \(17\) digits). Also note that taking too large upper bound may lead to an overflow.

The time complexity per test case is \(O(D \log 10^D) = O(D^2)\), where \(D\) is the number of digits in \(R\). (It may require an additional \(D\) (or in fact, avoid binary search to reduce one more \(D\)), but it is fast enough anyway.)

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

long long p10[18]={0};

long long number(long long i,long long k,string &s){
  long long l=s.size();
  long long r=k+1-l;
  if(r<0){return -1;}
  i--;
  if(s[0]=='0'){i+=p10[r];}

  long long p=i/p10[r];
  long long q=i%p10[r];

  return p*p10[k+1] + stoll(s)*p10[r] + q;
}

long long solve(long long x,string &s){
  int sl=s.size();
  long long res=0;
  for(long long k=0;k<=15;k++){
    long long first=number(1,k,s);
    if(first==-1){continue;} // not exist
    if(first>x){continue;} // too large
    long long l=1,r=p10[16-sl];
    while(l<=r){
      long long te=(l+r)/2;
      if(number(te,k,s)>x){r=te-1;}else{l=te+1;}
    }
    res+=r;
  }
  return res;
}

int main(){
  p10[0]=1;
  for(int i=1;i<18;i++){p10[i]=p10[i-1]*10;}

  int t;
  cin >> t;
  while(t>0){
    t--;
    string s;
    long long l,r;
    cin >> s >> l >> r;
    cout << solve(r,s) - solve(l-1,s) << "\n";
  }
  return 0;
}