E. Tim Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Since watching the game theory session, the secret partner has been beating Eddard in Nim Game every time. So, Eddard got bored and decided they should spice it up a little bit and make a new game with his favorite topic, trees! He decided to call the new game Tim Game, short for Tree Nim Game. He really doesn't know how to come up with creative names.

Eddard and his secret partner are playing a game where they are given a tree with $$$n$$$ nodes rooted at node $$$1$$$. The secret partner goes first, then they alternate turns.

Each turn, a player picks a node $$$u$$$ other than the root, and removes it and all its descendants.

The last player to make a move wins. Equivalently, the player who can't make a move on their turn loses.

Can you find out who will win if both play optimally?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 4 \cdot 10^5)$$$ – The size of the tree.

Each of the next $$$n-1$$$ lines describes an edge $$$(u, v)$$$ $$$(1 \le u, v \le n)$$$.

It is guaranteed that the given edges in each test case form a tree, and the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, print "The Secret Partner" if the secret partner wins. Otherwise, print "Eddard".

Example
Input
3
6
1 2
2 3
2 4
1 5
5 6
10
1 2
2 3
3 4
4 5
3 6
1 7
7 8
7 9
9 10
2
1 2
Output
The Secret Partner
The Secret Partner
The Secret Partner
Note

In the first test case, one possible scenario is the following:

  • The secret partner picks $$$3$$$ and removes it.
  • Eddard picks $$$2$$$ and removes it and its descendants $$$(4)$$$.
  • The secret partner picks $$$5$$$ and removes it and its descendants $$$(6)$$$.
  • Eddard can't make a move as only the root remains and loses.

In the second test case, one possible scenario is the following:

  • The secret partner picks $$$6$$$ and removes it.
  • Eddard picks $$$3$$$ and removes it and its descendants $$$(4, 5)$$$.
  • The secret partner picks $$$10$$$ and removes it.
  • Eddard picks $$$8$$$ and removes it.
  • The secret partner picks $$$9$$$ and removes it.
  • Eddard picks $$$2$$$ and removes it.
  • The secret partner picks $$$7$$$ and removes it.
  • Eddard can't make a move as only the root remains and loses, again.

No need to explain the third test case, The Secret Partner always wins anyway.