#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define n 100005
int arr[n];
void lsp(string s,int l){
int i = 0,j = 1;
arr[0] = 0;
while(j<l){
if(s[i] == s[j]){
i++;
arr[j] = i;
j++;
}else{
if(i!=0) i = arr[i-1];
else{
j++;
arr[i] = 0;
}
}
}
}
int main() {
int t;
cin>>t;
while(t--){
int len;
string s;
cin>>len>>s;
memset(arr,0,sizeof(arr));
lsp(s,len);
//cout<<"aman";
int a[len];
for(int i=0;i<=len;i++) a[i] = 0;
for(int i=0;i<n;i++){
if(arr[i]!=0){
a[arr[i]]++;
//debug(arr[i]);
}
}
int m = 0,ans;
for(int i=1;i<=len;i++){
if(a[i] >= m && a[i]!=0){
m = a[i];
ans = i;//cout<<i;
}
}
if(m) cout<<s.substr(0,ans);
else cout<<s;
cout<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSBkZWJ1Zyh4KSBjb3V0PDwjeDw8IiA6OiAiPDx4PDxlbmRsOwojZGVmaW5lIGRlYnVnMih4LHkpIGNvdXQ8PCN4PDwiIDo6ICI8PHg8PCJcdCI8PCN5PDwiIDo6ICI8PHk8PGVuZGw7CgojZGVmaW5lIG4gMTAwMDA1CmludCBhcnJbbl07Cgp2b2lkIGxzcChzdHJpbmcgcyxpbnQgbCl7CiAgaW50IGkgPSAwLGogPSAxOwogIGFyclswXSA9IDA7CiAgd2hpbGUoajxsKXsKICAgIGlmKHNbaV0gPT0gc1tqXSl7CiAgICAgIGkrKzsKICAgICAgYXJyW2pdID0gaTsKICAgICAgaisrOwogICAgfWVsc2V7CiAgICAgIGlmKGkhPTApIGkgPSBhcnJbaS0xXTsKICAgICAgZWxzZXsKICAgICAgICBqKys7CiAgICAgICAgYXJyW2ldID0gMDsKICAgICAgfQogICAgfQogIH0KfQoKaW50IG1haW4oKSB7CiAgaW50IHQ7CiAgY2luPj50OwogIHdoaWxlKHQtLSl7CiAgICBpbnQgbGVuOwogICAgc3RyaW5nIHM7CiAgICBjaW4+Pmxlbj4+czsKICAgIG1lbXNldChhcnIsMCxzaXplb2YoYXJyKSk7CiAgICBsc3AocyxsZW4pOwogICAgLy9jb3V0PDwiYW1hbiI7CiAgICBpbnQgYVtsZW5dOwogICAgZm9yKGludCBpPTA7aTw9bGVuO2krKykgYVtpXSA9IDA7CgogICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgIGlmKGFycltpXSE9MCl7CiAgICAgICAgYVthcnJbaV1dKys7CiAgICAgICAgLy9kZWJ1ZyhhcnJbaV0pOwogICAgICB9CiAgICB9CgogICAgaW50IG0gPSAwLGFuczsKICAgIGZvcihpbnQgaT0xO2k8PWxlbjtpKyspewogICAgICBpZihhW2ldID49IG0gJiYgYVtpXSE9MCl7CiAgICAgICAgbSA9IGFbaV07CiAgICAgICAgYW5zID0gaTsvL2NvdXQ8PGk7CiAgICAgIH0KICAgIH0KICAgIGlmKG0pIGNvdXQ8PHMuc3Vic3RyKDAsYW5zKTsKICAgIGVsc2UgY291dDw8czsKICAgIGNvdXQ8PGVuZGw7CgogIH0KICByZXR1cm4gMDsKfQo=