Doodle 和 Doddle 是两名喜欢一起玩游戏的机器人兄弟。 今天的游戏规则如下： 给定一棵有 $n$ 个节点的有根树，其中有 $m$ ($m \ge 3$) 个叶子节点（度数为 1 且不是根节点的节点），这些叶子节点被编号为 1 到 $m$ 的排列。 Doodle 和 Doddle 最初都站在根节点 $n$ 上，他们轮流执行以下操作，Doodle 先手： 如果当前节点是叶子节点，则什么都不做。 如果当前节点不是叶子节点，则选择树中的一个子节点并移动到该子节点。

当两名玩家都到达叶子节点时，游戏结束。设 Doodle 最终所在的叶子节点编号为 $x$，Doddle 最终所在的叶子节点编号为 $y$。 如果 $x \pmod m = (y + 1) \pmod m$，则 Doodle 获胜。 如果 $(x + 1) \pmod m = y \pmod m$，则 Doddle 获胜。 * 否则，平局。

Doodle 和 Doddle 都是极其聪明的机器人，因此他们一定会采取最优策略。请确定最终谁会获胜。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据： 第一行包含两个整数 $n$ ($4 \le n \le 10^5$) 和 $m$ ($3 \le m < n$)，分别表示树的节点数和叶子节点的数量。 接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示树中的一条边。 保证节点 $1, 2, \dots, m$ 正好是树的叶子节点，且节点 $n$ 是树的根节点。 保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一行 Doodle 或 Doddle，表示获胜者。如果游戏平局，输出一行 Tie。

样例

输入 1

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

输出 1

Tie
Doddle