#include<bits/stdc++.h>
#define ll long long
using namespace std ;

void change(string &s)
{
    for(int i = 0 ; i < s.size() ; i++)
    {
        if(s[i] == '0')
            s[i] = '1' ;
        else
            s[i] = '0' ;
    }
    return ;
}

void solve()
{
    string a ;
    ll n ;

    cin >> n >> a ;

    string s , t ;

    ll cnt[2] = {0 , 0} ;
    for(int i = 0 ; i < n ; i++)
        cnt[a[i] - '0']++ ;

    int flag = 0 ;

    if(cnt[0] < cnt[1])
    {
        flag = 1 ;
        change(a) ;
        swap(cnt[0] , cnt[1]) ;
    }

    t = a ;
    sort(t.begin() , t.end()) ;

    vector<ll> len(cnt[1]+1 , cnt[0]/(cnt[1]+1)) ;
    ll rem = cnt[0]%(cnt[1]+1) ;

    for(int i = ((int)len.size())-1; i >= 0 && rem > 0; i--)
    {
        len[i]++ ;
        rem-- ;
    }

    for(int i = 0 ; i < len.size() ; i++)
    {
        if(i)
            s += '1' ;
        for(int j = 0 ; j < len[i] ; j++)
            s += '0' ;
    }

    if(flag)
    {
        change(s) ;
        change(t) ;
    }
    cout << s << '\n' << t << endl ;
    return ;

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }

    return 0;
}