// Author: Aquizahv #include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define lnf 0x3f3f3f3f using namespace std; const int N = 1e5 + 5, LOGN = 18, CH = 128; int n, m; char s[N], mx[N], mn[N]; int cnt[CH][N], L[N]; int stk[N], tp; int getcnt(int l, int r, int c) { return cnt[c][r] - cnt[c][l - 1]; } #define white puts("POSSIBLE") #define black puts("IMPOSSIBLE") void checkn() { for (int i = 1; i < n; i++) if (s[i] > s[i + 1]) { white; for (int j = 1; j <= n; j++) printf("%c%c", s[j], " \n"[j == n]); return; } black; } void check2() { for (int i = 1; i < n; i++) { if (mn[i] > mx[i + 1] || (mn[i] == mx[i + 1] && (getcnt(1, i, mn[i]) > getcnt(i + 1, n, mx[i + 1]) || getcnt(1, i, mn[i]) != i))) { white; for (int j = 1; j <= n; j++) putchar(s[j]), (j == i ? putchar(' ') : (j == n ? putchar('\n') : 0)); return; } } black; } void check3() { for (int i = 1; i < n - 1; i++) { if (s[i + 1] < mn[i] || (i > 1 && s[i + 1] == mn[i])) { white; for (int j = 1; j <= n; j++) putchar(s[j]), (j == i || j == i + 1 ? putchar(' ') : (j == n ? putchar('\n') : 0)); return; } } for (int i = 2; i < n; i++) { int l = L[i + 1] + 1; if (l > i || mx[i + 1] > s[i]) continue; if (getcnt(l, i, mx[i + 1]) < i - l + 1 || getcnt(l, i, mx[i + 1]) > getcnt(i + 1, n, mx[i + 1])) { cout << i << ' ' << l << endl; white; for (int j = 1; j <= n; j++) putchar(s[j]), (j == l - 1 || j == i ? putchar(' ') : (j == n ? putchar('\n') : 0)); return; } } black; } void check4() { for (int i = 1; i < n; i++) if (s[i] > s[i + 1]) { white; int cnt1 = min(m - 4, i - 2); int cnt2 = min(m - 4 - cnt1, n - i - 2); for (int j = 1; j <= n; j++) { putchar(s[i]); if (j < i - 1) cnt1 > 0 ? putchar(' '), cnt1-- : 0; else if (i - 1 <= j && j <= i + 1) putchar(' '); else cnt2 > 0 ? putchar(' '), cnt2-- : 0; } return; } for (int i = 2; i < n; i++) if (s[i - 1] == s[i] && s[i] == s[i + 1]) { white; int cnt1 = min(m - 4, i - 3); int cnt2 = min(m - 4 - cnt1, n - i - 2); for (int j = 1; j <= n; j++) { putchar(s[i]); if (j < i - 2) cnt1 > 0 ? putchar(' '), cnt1-- : 0; else if (i - 2 <= j && j <= i + 1) i != i - 1 ? putchar(' ') : 0; else cnt2 > 0 ? putchar(' '), cnt2-- : 0; } } black; } void solve() { scanf("%d%s", &m, s + 1); n = strlen(s + 1); for (int i = 1; i <= n; i++) { for (char j = 'A'; j <= 'Z'; j++) cnt[j][i] = cnt[j][i - 1]; cnt[s[i]][i]++; } mn[0] = 'a'; for (int i = 1; i <= n; i++) mn[i] = min(mn[i - 1], s[i]); for (int i = n; i >= 1; i--) mx[i] = max(mx[i + 1], s[i]); tp = 0; for (int i = 1; i <= n; i++) { while (tp > 0 && s[stk[tp]] >= s[i]) tp--; L[i] = stk[tp]; stk[++tp] = i; } if (m == n) { checkn(); return; } if (m == 2) check2(); if (m == 3) check3(); if (m >= 4) check4(); } int main() { freopen("cut.in", "r", stdin); freopen("cut.out", "w", stdout); int T; cin >> T; for (int i = 1; i <= T; i++) { printf("Case #%d: ", i); solve(); } return 0; }