#include<bits/stdc++.h>
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::string s,res; std::cin >> s;
        int cnta = std::count(s.begin(), s.end(), 'A'), cntb = std::count(s.begin(), s.end(), 'B');
        int cntn = std::count(s.begin(), s.end(), 'N');
        while (cnta || cntb || cntn) {
            if (cntn) res += 'N', cntn--;if (cntb) res += 'B', cntb--;
            if (cnta) res += 'A', cnta--;
        }
        std::cout << "case #" << i << ":\n" << res<<'\n';
        res.clear(), s.clear();
    }
    return 0;
}