Problem: This is an interactive problem.

Baby Ehab loves crawling around his apartment. It has n rooms numbered from 0 to n-1. For every pair of rooms, a and b, there's either a direct passage from room a to room b, or from room b to room a, but never both.

Baby Ehab wants to go play with Baby Badawy. He wants to know if he could get to him. However, he doesn't know anything about his apartment except the number of rooms. He can ask the baby sitter two types of questions: 

  * is the passage between room a and room b directed from a to b or the other way around? 
  * does room x have a passage towards any of the rooms s_1, s_2, ..., s_k? 



He can ask at most 9n queries of the first type and at most 2n queries of the second type.

After asking some questions, he wants to know for every pair of rooms a and b whether there's a path from a to b or not. A path from a to b is a sequence of passages that starts from room a and ends at room b.

Input

The first line contains an integer t (1 ≤ t ≤ 30) — the number of test cases you need to solve.

Then each test case starts with an integer n (4 ≤ n ≤ 100) — the number of rooms.

The sum of n across the test cases doesn't exceed 500.

Output

To print the answer for a test case, print a line containing "3", followed by n lines, each containing a binary string of length n. The j-th character of the i-th string should be 1 if there's a path from room i to room j, and 0 if there isn't. The i-th character of the i-th string should be 1 for each valid i.

After printing the answer, we will respond with a single integer. If it's 1, you printed a correct answer and should keep solving the test cases (or exit if it is the last one). If it's -1, you printed a wrong answer and should terminate to get Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Interaction

To ask a question of the first type, use the format: 

  * 1 a b (0 ≤ a,b ≤ n-1, a ≠ b). 
  * we will answer with 1 if the passage is from a to b, and 0 if it is from b to a. 
  * you can ask at most 9n questions of this type in each test case. 



To ask a question of the second type, use the format: 

  * 2 x k s_1 s_2 ... s_k (0 ≤ x,s_i ≤ n-1, 0 ≤ k < n, x ≠ s_i, elements of s are pairwise distinct). 
  * we will answer with 1 if there's a passage from x to any of the rooms in s, and 0 otherwise. 
  * you can ask at most 2n questions of this type in each test case. 



If we answer with -1 instead of a valid answer, that means you exceeded the number of queries or made an invalid query. Exit immediately after receiving -1 and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see the documentation for other languages.



Hacks:

The first line should contain an integer t — the number of test cases.

The first line of each test case should contain an integer n (4 ≤ n ≤ 100) — the number of rooms.

Each of the next n lines should contain a binary string of length n. The j-th character of the i-th string should be 1 if there's a passage from room i to room j, 0 otherwise. The i-th character of the i-th string should be 0.

Example

Input


1
4

0

0

1

1

1

Output


2 3 3 0 1 2

1 0 1

1 0 2

2 2 1 1

3
1111
1111
1111
0001

Note

In the given example:

<image>

The first query asks whether there's a passage from room 3 to any of the other rooms.

The second query asks about the direction of the passage between rooms 0 and 1.

After a couple other queries, we concluded that you can go from any room to any other room except if you start at room 3, and you can't get out of this room, so we printed the matrix:
    
    
      
    1111  
    1111  
    1111  
    0001  
    

The interactor answered with 1, telling us the answer is correct.

Solution (in CPP):

Solution:
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif
#undef endl
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
// #define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    std::vector<int> parent_or_size;
};

}  // namespace atcoder


bool type1(lli a,lli b){
    cout<<"1 "<<a<<" "<<b<<endl;
    cin>>a;
    if(a==-1)
        exit(0);
    return a;
}

bool type2(const vi &a,lli b){
    cout<<"2 "<<b<<" "<<sz(a);
    for(auto x:a)
        cout<<" "<<x;
    cout<<endl;
    cin>>b;
    if(b==-1)
        exit(0);
    return b;
}

vi solve(lli l,lli r){
    if(l==r)
        return {l};
    lli mid=(l+r)/2;
    vi ans;
    auto a=solve(l,mid);
    auto b=solve(mid+1,r);
    const int n=sz(a),m=sz(b);
    lli i=0,j=0;
    while(i<n&&j<m){
        if(type1(a[i],b[j]))
            ans.pb(a[i++]);
        else
            ans.pb(b[j++]);
    }
    while(i<n){
        ans.pb(a[i++]);
    }
    while(j<m){
        ans.pb(b[j++]);
    }
    return ans;
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
cin>>T;while(T--)
{

    cin>>n;
    auto a=solve(0,n-1);
    lli l=n-2,r=n-1;
    atcoder::dsu d(n);
    vi id(n);
    for(int i=0;i<n;++i)
        id[a[i]]=i;
    while(r>0&&l>=0){
        l=min(l,r-1);
        if(l<0)
            break;
        auto b=a;
        b.resize(l+1);
        if(type2(b,a[r])){
            d.merge(a[l],a[r]);
            l--;
        } else {
            r--;
        }
    }
    dbg(d.groups());
    cout<<"3"<<endl;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j){
            if(d.same(i,j)||id[i]<=id[j]){
                cout<<"1";
            } else {
                cout<<"0";
            }
        }
        cout<<endl;
    }
    cin>>n;
    if(n==-1)
        exit(0);
}   aryanc403();
    return 0;
}