#include<algorithm>
#include<iostream>
using namespace std;
const int INF= (1<<30);
const int MAX=30;
struct point{
    int w,d;
};
struct Node{
    int id,flow;
    Node*next;
};
Nodenode[MAX*MAX],edge[MAX*MAX*MAX],*mat[MAX*MAX];
point p[MAX];
int ma[MAX][MAX],Q[MAX*MAX],pre[MAX*MAX];
bool vis[MAX*MAX];
int N,edge_n,S,T;
inline int Min(int a,int b){
    return a<b?a:b;
}
void init(){
    edge_n=0;
    for(int i=0;i<=T;i++)
        node[i].next=NULL;
}
void add(int fr,int to,int flow){
    edge[edge_n].id=to;
    edge[edge_n].flow=flow;
    edge[edge_n].next=node[fr].next;
    node[fr].next=&edge[edge_n];
    edge_n++;
    edge[edge_n].id=fr;
    edge[edge_n].flow=0;
    edge[edge_n].next=node[to].next;
    node[to].next=&edge[edge_n];
    edge_n++;
}
Node*reverse(Node*pp){
    return edge+((pp-edge)^1);
}
bool findpath(){
    memset(vis,false,sizeof(vis));
    int fr=0,re=1;
    vis[S]=true;
    while(fr<re){
        int v=Q[fr++];
        for(Node*cur=node[v].next;cur;cur=cur->next){
            int id=cur->id;
            if(cur->flow<=0) continue;
            if(!vis[id]){
               vis[id]=true;
               Q[re++]=id;
               pre[id]=v;
               mat[id]=cur;
               if(id==T)return true;
            }
        }    
    }
    return false;
}
int maxflow(){
    int ans=0;
    while(findpath()){
        int j=T,now=INF;
        while(j!=S){
           now=Min(now,mat[j]->flow);
            j=pre[j];
        }
        ans+=now;
        j=T;
        while(j!=S){
           mat[j]->flow-=now;
           reverse(mat[j])->flow+=now;
            j=pre[j];
        }
    }
    return ans;
}
bool check(int id){
    init();
    int m[MAX][MAX];
    S =0,T= N+300+1;
    int tmp= p[id].w;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
           m[i][j]=ma[i][j];
    for(i=1;i<=N;i++)
        if(m[id][i]){
           tmp+=m[id][i];
           m[id][i]=m[i][id]=0;
        }
    int num=0,cur=0;
    for(i=1;i<=N;i++){
        for(int j=i+1;j<=N;j++){
            if(m[i][j]){
               num++;
               cur+=m[i][j];
               add(S,num,ma[i][j]);
               add(num,300+i,m[i][j]);
               add(num,300+j,m[i][j]);
            }
        }
        if(tmp<p[i].w) return false;
        if(tmp>p[i].w)
        add(i+300,T,tmp- p[i].w);
    }
    return cur==maxflow();
}
void readIn(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&p[i].w,&p[i].d);
    for(i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            scanf("%d",&ma[i][j]);
    return;
}
void Solve(){
    bool flag=true;
    for(int i=1;i<=N;i++){
        if(check(i)){
            if(flag) printf("%d",i);
            else printf(" %d",i);
            flag=false;
        }
    }
    printf("\n");
    return;
}
int main(){
    int Cas;
    scanf("%d",&Cas);
    while(Cas--){
        readIn();
        Solve();    
    }
}