#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int m;string s; int c1[26],c2[26]; int sm[maxn][26]; int pre[maxn]; int stk[maxn]; void slv(){ cin>>m>>s; int n=s.size(); if(m==s.size()){ up(i,0,n-2)if(s[i]>s[i+1]){ printf("POSSIBLE\n"); for(char c:s)printf("%c ",c);printf("\n"); return; } return printf("IMPOSSIBLE\n"),void(); } if(m>=4){ up(i,0,n-2)if(s[i]>s[i+1]){ set<int>P={i}; if(i+1!=n-1)P.insert(i+1); up(j,0,n-2){ if(P.count(j))continue; if(P.size()<m-1)P.insert(j); else break; } printf("POSSIBLE\n"); P.insert(n-1); int p=0; for(int u:P){ printf("%s ",s.substr(p,u-p+1).c_str()); }printf("\n"); return; } up(i,0,n-3)if(s[i]==s[i+1]&&s[i+1]==s[i+2]){ set<int>P={i}; if(i+2!=n-1)P.insert(i+2); up(j,0,n-2){ if(P.count(j))continue; if(P.size()<m-1)P.insert(j); else break; } printf("POSSIBLE\n"); P.insert(n-1); int p=0; for(int u:P){ printf("%s ",s.substr(p,u-p+1).c_str());p=u+1; }printf("\n"); return; } return printf("IMPOSSIBLE\n"),void(); } if(m==2){ memset(c1,0,sizeof(c1)),memset(c2,0,sizeof(c2)); up(i,0,n-1)c2[s[i]-'A']++; up(i,0,n-2){ c2[s[i]-'A']--,c1[s[i]-'A']++; int l=0,r=25; while(!c1[l])l++; while(!c2[r])r--; if(l>r||(l==r&&(c1[l]>c2[r]||(c1[l]==c2[r]&&c1[l]<i+1))))return printf("POSSIBLE\n%s %s\n",s.substr(0,i+1).c_str(),s.substr(i+1,n-(i+1)).c_str()),void(); } return printf("IMPOSSIBLE\n"),void(); } else {memset(c1,0,sizeof(c1)),memset(c2,0,sizeof(c2)); up(i,0,n-3){ c1[s[i]-'A']++;c2[s[i+1]-'A']=1; int l=0,r=25; while(!c1[l])l++; while(!c2[r])r--; if(l>r||(l==r&&(c1[l]>c2[r]||(c1[l]==c2[r]&&c1[l]<i+1))))return printf("POSSIBLE\n%s %s %s\n",s.substr(0,i+1).c_str(),s.substr(i+1,1).c_str(),s.substr(i+2,n-(i+2)).c_str()),void(); c2[s[i+1]-'A']=0; } memset(c1,0,sizeof(c1)); memset(sm,0,sizeof(sm));sm[0][s[0]-'A']=1; up(i,1,n-1){ memcpy(sm[i],sm[i-1],sizeof(sm[i])); sm[i][s[i]-'A']++; } auto init=[](int l,int r){ up(i,0,25)c1[i]=sm[r][i]-(l?sm[l-1][i]:0); };int tp=0;stk[0]=-1; up(i,0,n-1){ while(tp&&s[stk[tp]]>=s[i])tp--; pre[i]=stk[tp];stk[++tp]=i; } down(i,n-2,1){ c2[s[i+1]-'A']++; memset(c1,0,sizeof(c1)); int r=25; while(!c2[r])r--; if(s[i]-'A'<r)continue; if(s[i]-'A'>r)return printf("POSSIBLE\n%s %s %s\n",s.substr(0,i).c_str(),s.substr(i,1).c_str(),s.substr(i+1,n-(i+1)).c_str()),void(); int pos=max(pre[i]+1,1); init(pos,i); if(c1[r]>c2[r]||c1[r]!=i-pos+1)return printf("POSSIBLE\n%s %s %s\n",s.substr(0,pos).c_str(),s.substr(pos,i-pos+1).c_str(),s.substr(i+1,n-(i+1)).c_str()),void(); } printf("IMPOSSIBLE\n"); } } int main(){ //freopen("cut.in","r",stdin),freopen("cut.out","w",stdout); int t=read();up(i,1,t){ printf("Case #%d: ",i); slv(); } return 0; }