Time has come for Ma5termind and his friends Shasha and Alok to decide their job locations. To serve the above purpose better, they assumed that the whole country consist of N cities numbered from 1 to N. Each pair of cities is connected by a directed edge. For eg: A city numbered X is connected to some other city numbered Y by a directed edge i.e either edge X to Y is present or edge Y to X is present but not both are present.

Now ma5termind and his friends have to select different cities as their job locations but they want to select these cities in such a way that they form a cycle so that they can live close to each other.

Help them to determine whether its possible to select cities in this way or not. If its possible print "Aye" and if it's not possible print "Nae".

Input

First line of input contains an integer T denoting the number of test cases. First line of each test case contains an integer N denoting the number of cities. Next N lines of each test cases contains N space separated integers where j^th integer in j^th line is 1 if there exists a directed edge from city i to city j otherwise 0.

Output

For each test case, print the required answer in a new line.

Constraints

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 500
• Given graph does not contain any self loops and multiple edges and it has exactly N*(N-1)/2 values set to 1.

Scoring

• Subtask 1: 1 ≤ N ≤ 100 ( 20 pts )
• Subtask 2: 1 ≤ N ≤ 500 ( 80 pts )