\(\sum_{k=L}^{R} f(k)\) を求めるテクニックとして、 \(\sum_{k=1}^{R} f(k) - \sum_{k=1}^{L-1} f(k)\) に置き換えるというものがあります。
こうすることによって、 \(\sum_{k=1}^{X} f(k)\) が求まれば元の問題も解くことができるようになる上、実装も平易になることが多いので、以降は置き換えた後の問題を考えます。

求めるべきものをそのまま求めようとすると煩わしく見えますが、以下の言い換えを利用すると見通しがよくなります。(このように、うまく足し方を変えて数え上げるテクニックは「主客転倒」とも呼ばれます)
\(\sum_{k=1}^{X} f(k) = \) \(\sum_{k=0}^{15}\) ( \(10^{k}\) の位を先頭の文字として \(S\) が出現するような \(X\) 以下の正整数の個数 )
具体的に \(X=234,\) \(S=\) 22 とすると \(\sum_{k=1}^{234} f(k)\) を求める際、以下の手順を踏むことになります。

• \(1\) の位を先頭の文字として \(S\) が出現することはありません。
• \(10\) の位を先頭の文字として \(S\) が出現する\([1,234]\) の範囲内の整数は \(22,122,222\) です。
• \(10^2\) の位を先頭の文字として \(S\) が出現する\([1,234]\) の範囲内の整数は \(220,221,222,\dots,229\) です。
• \(10^3\) の位より上の位を先頭の文字として \(S\) が出現する\([1,234]\) の範囲内の整数はありません。

これより、求める和は \(13\) であることが分かります。

実は、 \(10^k\) の位を先頭の文字として \(S\) が出現する整数のうち小さい方から \(i\) 番目のものは容易に求められます。
\(k=3, S=\) 95 としたとき、条件を満たす整数は ??...??95?? という形になります。

• \(i=1\) の時、求める整数は \(9500\)
• \(i=13\) の時、求める整数は \(9512\)
• \(i=100\) の時、求める整数は \(9599\)
• \(i=101\) の時、求める整数は \(19500\)
• \(i=2023\) の時、求める整数は \(209522\)

このように、 ? に \(i-1\) を (右端を合わせて) 書き込んだ整数が求めるものになります。

但し、 \(S\) が 0 から始まる場合は注意が必要です。
\(k=3, S=\) 05 とした場合、 \(i=1\) の時、求める整数は \(10500\) となります。
上の場合と言い方を揃えるなら、 \(S\) の右側にある ? の数を \(r\) としたとき、 ? に書き込むべき整数が \(i-1 + 10^r\) に変化します。

これにより、二分探索を使うことで \(X\) 以下の正整数であって \(10^k\) の位を先頭の文字として \(S\) が出現するものがいくつあるかを数えることができました。あとは \(k\) を動かして総和を取ることによってこの問題に正解することができます。
なお、探索すべき範囲に注意してください。 \(S\) が \(l\) 文字の時、 \(10^{16-l}\) 番目までを考慮すればよいです(これよりも後ろのものは必ず \(17\) 桁以上になることが分かります)。逆に、この範囲を広く取りすぎるとオーバーフローします。

テストケース当たりの時間計算量は \(R\) の桁数を \(D\) として \(O(D \log 10^D) = O(D^2)\) です。(方針によっては余計な \(D\) が付きます (し、実は逆に二分探索を回避して \(D\) を更に落とすことも可能です) が、それでも高速です)

実装例 (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;
}