f-friends-network

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 )

SAMPLE INPUT
2
3
0 1 1
0 0 1
0 0 0
3
0 1 0
0 0 1
1 0 0

SAMPLE OUTPUT
Nae
Aye

Explanation

Test 1: It is not possible to select such triplet of cities.
Test 2: It is possible to select such triplet of cities that form a simple cycle.

Source: hackerearth | Difficulty: EASY


Solutions: