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[0]).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.

Input
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.

Output
For every test case, a single integer denoting the maximum profit as described above.

Constraints
T<=60
N<=50
0<=VAL[i]<1023 for all 0<=i
Sample Input
``` 2 5 0 7 11 5 2 NYNYY YNYNN NYNNN YNNNN YNNNN 1 556 N ```

Sample Output
``` 14 556 ```

Problem Setter : Arjun Singh Bhatia

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0