#ifdef WTSH #include <wtsh.h> #else #include <bits/stdc++.h> using namespace std; #define dbg(...) #endif #define int long long #define endl "\n" #define sz(w) (int)(w.size()) using pii = pair<int, int>; const long long INF = 1e18; const int N = 1e6 + 5; // -------------------- Input Checker Start -------------------- long long readInt(long long l, long long r, char endd) { long long x = 0; int cnt = 0, fi = -1; bool is_neg = false; while(true) { char g = getchar(); if(g == '-') { assert(fi == -1); is_neg = true; continue; } if('0' <= g && g <= '9') { x *= 10; x += g - '0'; if(cnt == 0) fi = g - '0'; cnt++; assert(fi != 0 || cnt == 1); assert(fi != 0 || is_neg == false); assert(!(cnt > 19 || (cnt == 19 && fi > 1))); } else if(g == endd) { if(is_neg) x = -x; if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(false); } return x; } else { assert(false); } } } string readString(int l, int r, char endd) { string ret = ""; int cnt = 0; while(true) { char g = getchar(); assert(g != -1); if(g == endd) break; cnt++; ret += g; } assert(l <= cnt && cnt <= r); return ret; } long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); } long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); } string readStringLn(int l, int r) { return readString(l, r, '\n'); } string readStringSp(int l, int r) { return readString(l, r, ' '); } void readEOF() { assert(getchar() == EOF); } vector<int> readVectorInt(int n, long long l, long long r) { vector<int> a(n); for(int i = 0; i < n - 1; i++) a[i] = readIntSp(l, r); a[n - 1] = readIntLn(l, r); return a; } // -------------------- Input Checker End -------------------- bool check(string &s) { for(char c: s) if(c == ' ') return false; for(int i = 0; i + 2 < sz(s); i++) if(s[i] == s[i + 2]) return false; for(int i = 0; i + 1 < sz(s); i++) if(s[i] == s[i + 1]) return false; return true; } int sumN = 0; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int T = readIntLn(1, 1e5); while(T--) { int n = readIntLn(1, 1e5); sumN += n; string s = readStringLn(n, n); assert(*min_element(s.begin(), s.end()) >= 'a' and *max_element(s.begin(), s.end()) <= 'z'); int f[26] = {}; for(char c: s) f[c - 'a']++; vector<pair<int, char>> v; for(int i = 0; i < 26; i++) v.push_back({f[i], 'a' + i}); sort(v.begin(), v.end(), greater{}); int cntmx = 0; for(auto &[cnt, c]: v) cntmx += cnt == (n + 2) / 3; int allowed = n % 3; if(allowed == 0) allowed += 3; if(v[0].first <= (n + 2) / 3 and cntmx <= allowed) { cout << "YES\n"; string ans(n, ' '); string have = ""; for(auto [cnt, c]: v) have += string(cnt, c); int limit = ((n % 3 == 0) ? n - 1 : n); int cur = 0; for(int i = 0; i < limit; i++, cur = (cur + 3) % limit) { ans[cur] = have[i]; } if(n % 3 == 0) { ans[n - 1] = have[n - 1]; if(ans[n - 1] == ans[n - 2] or ans[n - 1] == ans[n - 3]) swap(ans[n - 1], ans[0]); } cout << ans << endl; assert(check(ans)); } else cout << "NO\n"; } readEOF(); assert(sumN <= 2e5); return 0; }