Sunny, the best Gamer of 2k10 :P, is playing a game.For a change this is a physical game as compared to his dark room lonely games.In This game he travels between cities and collects profits. It is allowed to visit each of the cities multiple times.
There are N cities numbered 0 through N-1. Each city has an associated value.Lets Assume that this Associated values are given in an array named VAL. There are also zero or more bidirectional roads connecting the cities.Each road connects exactly two different cities and can be traversed in both ways.
In this game , Sunny starts at city 0 with initial profit of value associated with city 0(i.e VAL).Sunny wants to maximize his final profit. At any time in the game , he may either End the Game and his current profit becomes his final profit, or Move to another city by traversing a single road. This is the interesting part of the game: assume that his current profit is P and the destination city is city X. After traversing the road, he will be at city X with profit P XOR VAL[X].
He wants you to help him calculate this maximum profit.
First Line of Input contains T denoting number of test cases T.
Every Test case begins with a single Integer N denoting number of cities.
Next line contains N space separated Integers denoting the array VAL as described above.
Then an Adjacency Matrix of N Rows and N columns is presented in the Next N lines, where Adj[i][j]=Y if there is a direct road connecting city i and j and Adj[i][j]=N otherwise.
For every test case, a single integer denoting the maximum profit as described above.
0<=VAL[i]<1023 for all 0<=i
0 7 11 5 2
Problem Setter : Arjun Singh Bhatia