博弈论是计算机科学的一个重要分支。因此，对于计算机专业的大学生来说，玩游戏并不总是一件令人愉快的事情。

今天，Rikka 正在研究一个关于树的简单而有趣的游戏。

考虑一棵有根树 $T$。初始时，根节点上有一个棋子。两名玩家在这棵树上进行游戏，轮流移动棋子。在每一轮中，假设棋子当前位于顶点 $i$，玩家需要选择 $i$ 的一个子节点 $j$，并将棋子移动到 $j$。如果 $i$ 没有子节点，游戏立即结束。

游戏的最终得分是棋子最终位置的深度（根节点的深度为 1，其他每个顶点的深度为其父节点深度加 1）。先手玩家希望最大化得分，而后手玩家希望最小化得分。假设两名玩家都采取最优策略。

给定一棵有根树 $T$，计算游戏的最终得分是一个简单的任务。因此，Rikka 想要解决一个更具挑战性的问题。她可以对树进行一些操作：每次操作，她可以选择树的一个叶子节点 $i$（叶子节点是指没有子节点的顶点），并连接一个新节点到树上，以 $i$ 作为其父节点。

设 $f(k)$ 为使得游戏最终得分恰好为 $k$ 所需的最少操作次数，假设两名玩家都采取最优策略。如果无法做到，则令 $f(k) = -1$。Rikka 想要知道 $\lim_{k \to +\infty} \frac{f(k)}{k}$ 的值。

你知道，Rikka 擅长提问，但不擅长回答。所以，她向你寻求帮助。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

接下来 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述树的一条边 $(u, v)$。根节点的编号为 1。

保证给定的图是树。同时保证 $n > 1000$ 的测试用例不超过 10 个。

输出格式

对于每个测试用例，输出一行一个整数：Rikka 想要知道的极限值。（事实证明，如果答案存在，它是一个整数。）如果极限不存在，则输出 $-1$。

样例

输入 1

1
8
1 2
2 3
2 4
4 5
4 8
5 6
5 7

输出 1

2