可以证明答案是 \(l\) 或 \(r\) 的一段前缀，拼上后面全部相同的一段字符 \(d\)，证明方式类似数位 dp。能够自由填的数字一定是相等的，这样不会影响幸运值。前面那些不能自由填写的，就是 \(l\) 或 \(r\) 的一段前缀。假如不是 \(l\) 或 \(r\) 的一段前缀，必然填写相等的更好，而这种情况已经被考虑到了。
枚举前缀长度，枚举修改成的字符 \(d\)，复杂度 \(\mathcal O(T\log^2w\Sigma)\)，字符集大小为 \(10\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
using std::cin;using std::cout;
using std::max;using std::min;
using loli=long long;
int n;
loli l,r;
std::vector<int>b1,b2,t,ans;
int calc(std::vector<int>b){
reverse(all(b));
while(!b.empty()&&!b.back())b.pop_back();
return *max_element(all(b))-*min_element(all(b));
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);cin.tie(nullptr);
int T;cin>>T;while(T--){
cin>>l>>r;
b1.clear();b2.clear();
ans.clear();
for(;l;l/=10)b1.push_back(int(l%10));
for(;r;r/=10)b2.push_back(int(r%10));
n=max(siz(b1),siz(b2));
while(siz(b1)<n)b1.push_back(0);
while(siz(b2)<n)b2.push_back(0);
reverse(all(b1));reverse(all(b2));
for(int k=0;k<=n;k++)for(int d=0;d<=9;d++){
t=b1;
for(int j=k;j<n;j++)t[j]=d;
if(b1<=t&&t<=b2&&(ans.empty()||calc(t)<calc(ans)))
ans=move(t);
}
for(int k=0;k<=n;k++)for(int d=0;d<=9;d++){
t=b2;
for(int j=k;j<n;j++)t[j]=d;
if(b1<=t&&t<=b2&&(ans.empty()||calc(t)<calc(ans)))
ans=move(t);
}
reverse(all(ans));
while(!ans.empty()&&!ans.back())ans.pop_back();
reverse(all(ans));
for(int i:ans)cout<<i;
cout<<'\n';
}
return 0;
}