Chef has a rooted tree G, consisting of N vertices. Each edge of the tree has a color black or white.
Once Chef's friend Ksen offered Chef to play a game on the tree G. The game has very simple rule:

The players make moves in the game alternately.
On his move Chef deletes a single undeleted black edge. On her move Ksen deletes a single undeleted white edge.
When some edge has been deleted, all the edges that now aren't connected (directly or indirectly) to the root will be deleted too.
One who cannot move lose the game.

Chef really likes the game. The only problem is that Ksen knows the game very well. So she always plays optimally. That's why Chef has decided to choose the order of moves. Help Chef: tell him who will win the game if he moves first, and also who will win the game if Ksen moves first. Consider that Chef plays optimally too.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each testcase contains a single integer N. Then N - 1 lines follows. Each contains three integers Ui, Vi, Ci. These integers denotes the current edge of the tree: the first two numbers means the numbers of vertices connected by the edge, the last number denotes the color of the edge (zero means black, one means white). Consider all vertices of the tree G are numbered from 1 to N. The root has number 1.

Output
For each test case, output a single line containing two strings: the name of the winner if Chef moves first, and the name of the winner if Chef moves second.

Constraints

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
1 ≤ Ui, Vi ≤ N
0 ≤ Ci ≤ 1
It's guaranteed that the sum of N values for all tests doesn't exceed 100000.

Example
Input:
5
1
2
1 2 0
2
1 2 1
3
1 2 0
1 3 1
3
1 2 0
2 3 1

Output:
Ksen Chef
Chef Chef
Ksen Ksen
Ksen Chef
Chef Chef

见题面

见题面