#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){string s;cin>>s;//s =  s;ll t;cin>>t;//t--;ll pos,k;ll len = 0;for(int i = 0 ; i < s.length() ; i++){if(len + s.length() - i >= t){pos = t - len;//第几个字符k = i;//这段删除几个break;}else{len += s.length() - i;}}//cout<<pos<<k;//每次先将前面的删掉 ， 先被删掉的应该是首个字典序小于的//如果s[i] < s[i-1]  就删掉 i - 1 是他目前存在的上一个string res;for(auto x : s){while (k > 0 && res.length() && x < res.back()){res.pop_back();k--;}res.push_back(x);}cout<<res[pos - 1];
}int main(){int t;cin>>t;while(t--){solve();}
}

先考虑如果让变化后的字符串最小，考虑

a b d a b c

观察到 再前面的位置使得字典序改变，字典序最小

当s[i] < s[i-1] 将i-1删除这样s[i] 就会到 i-1的位置

a b d a b c

a b a b c

观察删除后的字符串，发现并不需要从头开始计算，只需要从连接处在进行比较，

a b a b c

a a b c

可以通过一个单调栈进行维护，或者单链表也可以

计算一下最多删除多少个数