UVA 10705

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

const int OO = 1e9;
const double EPS = 1e-9;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        ll k;
        string s;
        ll n;
        cin >> k >> s >> n;
        if(n < 0) {
            n *= -1;
            for(int i = 0; i < s.size(); i++) {
                s[i] = (s[i] == 'p' ? 'n':'p');
            }
        }
        unsigned ll ans = 0;
        unsigned ll req = n;
        unsigned ll sum = 0;
        reverse(s.begin(),s.end());
        unsigned ll mx = 0;
        for(unsigned ll i = 0; i < s.size(); i++) {
            if(s[i] == 'p')
                mx += ((unsigned ll) 1 << i);
        }
        if(n > mx) {
            cout << "Impossible";
        }
        else {
            for(unsigned ll i = 0; i < s.size(); i++) {
                //cout << "req is " << req << "\n";
                if(req%2) {
                    ans |= ((unsigned ll) 1 << i);
                    //sum += (s[i] == 'n' ? -1:1)*((unsigned ll)1 << i);
                    if(req%2 && s[i] == 'n') {
                        req /= 2;
                        req ++;
                    }
                    else {
                        req /= 2;
                    }
                }
                else {
                    req /= 2;
                }

            }
            for(unsigned ll i = s.size()-1; i >= 0; i--) {
                cout << (ans&((unsigned ll)1 << i) ? '1':'0');
                if(!i)
                    break;
            }
        }

        cout << "\n";
    }
    return 0;
}