In a country with $N$ cities, Alice wishes to start a legendary journey. She wants to start from one city, move to an adjacent city each time, and visit exactly $K$ cities without repeating any city along the way, finally ending at another city. Note that the starting city and the ending city are also considered visited cities, meaning all cities visited, including the start and end, must be distinct.

Now, Alice wants to know which pairs of cities $(u, v)$ can serve as the starting and ending cities of the journey.

Input

The first line contains a single integer $T$, representing the number of test cases.

For each test case, the first line contains three integers $N$, $M$, and $K$, representing the number of cities, the number of adjacency relationships between cities, and the number of cities that must be visited during the journey, respectively.

Following this are $M$ lines, each containing two integers $u$ and $v$, indicating that city $u$ and city $v$ are adjacent.

Output

For each test case, output $N$ lines, each containing $N$ characters.

The $j$-th character of the $i$-th line should be "Y" or "N", indicating whether there exists a valid journey starting at city $i$ and ending at city $j$.

Constraints

• For 5% of the data, $K \le 2$.
• For 15% of the data, $K \le 3$.
• For 35% of the data, $K \le 4$.
• For 55% of the data, $K \le 5$.
• For 75% of the data, $K \le 6$.
• For 100% of the data, $N \le 1000$, $M \le 5000$, $2 \le K \le 7$, and $T \times \lfloor K/2 \rfloor \le 60$.

Examples

Input 1

1
5 6 4
1 2
2 3
3 5
1 4
4 5
2 5

Output 1

NYYYY
YNNYY
YNNYN
YYYNY
YYNYN