The new season of the Bytelandian Premier League (BPL) has started!
In the BPL, any two soccer teams play with each other exactly once. In each match, the winner earns 3 points and the loser earns no point. There is no draw (if the match is level after the two halves, two teams will take part in a penalty shootout to decide the winner).
At the end of the league, the winner is the team having the largest number of points. In case there are more than one team which has the largest number of points, these teams will be co-champions of the league.
The league has been running for some time. Now, the following problem has arisen: we would like to know if a specific team still has a chance of winning the league.

Input
The first line contains T (about 20), the number of test cases. Then T test cases follow. Each test case has the following form.
The first line of the test case contains a number N (1 ≤ N ≤ 140), the number of teams in the league.
The i-th line in the next N lines contains N numbers ai1, ai2, ..., ain. The number aij gives the status of the match between the i-th team and the j-th team:

aij = 1 if the i-th team wins,
aij = 0 if the i-th team loses,
aij = 2 if the match has not taken place yet.

The input data is such that if i!=j, then aij + aji = 1 or aij = aji = 2. Moreover, aii = 0 for all i.  


Output
For each test case, print a binary string of length N, in which the i-th character is 1 if the i-th team still has a chance to be a champion of the league, and 0 otherwise.

Example

Input:
3
3
0 0 0 
1 0 1 
1 0 0 
4
0 1 1 0 
0 0 2 0 
0 2 0 0 
1 1 1 0 
5
0 2 2 1 0 
2 0 1 1 0 
2 0 0 1 0 
0 0 0 0 1 
1 1 1 0 0 

Output:
010
0001
11001
#!/usr/bin/python
# Richard Lee
import os
import sys

def champion_possible(team_id, r_m, c_list):
   def team_sort(x, y):
      rx = r[x]
      ry = r[y]
      if rx == ry:
         return p[y] - p[x]
      return rx - ry
   
   def team_sort_r(x, y):
      rx = r[x]
      ry = r[y]
      if rx == ry:
         return p[x] - p[y]
      return ry - rx
   
   r, p, t_a = r_m
   team_sz = len(c_list)
   r[team_id] += p[team_id]
   p[team_id] = 0
   t_r = t_a[team_id]
   while len(t_r) > 0:
      j = t_r.pop()
      p[j] -= 1
      t_a[j].remove(team_id)
   
   c_win = True
   t_l = [i for i in xrange(team_sz)]
   t_l.remove(team_id)
   t_l = sorted(t_l, lambda x,y: team_sort(x,y))
   while len(t_l) > 0:
      t_i = t_l.pop()
      t_r = t_a[t_i]
      t_s = r[t_i] + p[t_i]
      if t_s > r[team_id]:
         t_r = sorted(t_r, lambda x,y: team_sort_r(x,y))
         t_r_sz = len(t_r)
         d = t_s - r[team_id]
         for i in xrange(0, t_r_sz):
            t_low = t_r.pop()
            if r[t_low] + 1 <= r[team_id]:
               p[t_i] -= 1
               p[t_low] -= 1
               r[t_low] += 1
               d -= 1
               t_a[t_low].remove(t_i)
            else:
               t_r.append(t_low)
            if d == 0:
               break
      r[t_i] += p[t_i]
      if r[t_i] > r[team_id]:
         c_win = False
         break
      elif p[t_i] > 0:
         while len(t_r) > 0:
            t_low = t_r.pop()
            p[t_low] -= 1
            t_a[t_low].remove(t_i)
   if c_win:
      for i in xrange(team_sz):
         if r[i] == r[team_id]:
            c_list[i] = 1
   
      
   
tc = int(sys.stdin.readline())
for t_i in xrange(tc):
   teamcount = int(sys.stdin.readline())
   max_s = 0
   r = [0 for i in xrange(teamcount)]
   t = r[:]
   p = r[:]
   champ_list = r[:]
   
   for i in xrange(teamcount):
      l = sys.stdin.readline().rstrip()
      l_p = l.split()
      t_r = []
      for j in xrange(teamcount):
         c = int(l_p[j])
         if c == 1:
            r[i] += 1
         elif c == 2:
            p[i] += 1
            t_r.append(j)
      if r[i] > max_s:
         max_s = r[i]
      t[i] = t_r
   
   if max_s == 0:
      print 0
      continue
   
   for i in xrange(teamcount):
      if r[i] + p[i] >= max_s and not champ_list[i]:
         t_c = [0 for j in xrange(teamcount)]
         for j in xrange(teamcount):
            t_c[j] = t[j][:]
         champion_possible(i, (r[:],p[:],t_c), champ_list)

   s_o = ""
   for i in xrange(teamcount):
      s_o += "%i" %(champ_list[i])
   print s_o
   
   
exit(0)