Bob 的工作是维护一个网络，该网络可以表示为一个具有 $n$ 个节点和 $n$ 条无向边的连通图，但现在他必须关闭整个网络。

起初，所有节点都是活跃的。在关闭过程中，他会重复选择一个活跃节点并将其停用，直到没有活跃节点为止。然而，每个活跃节点都有一个表，存储了从该节点到任何其他活跃节点的连通性信息。当节点 $u$ 被停用时，每个曾经能够到达 $u$ 的活跃节点 $v$（包括 $u$ 本身）都必须更新其自身的表。每次更新可能会改变多条记录，因为每次停用都可能将一个连通分量切割成若干个较小的连通分量，但每次更新的代价几乎相同——即从 $v$ 进行一次广度优先搜索。

现在 Bob 想知道他应该以什么顺序关闭这些节点，因为他知道如果操作顺序不当，更新次数会非常多。他不擅长寻找最优解，因此他选择在任何时候都以相等的概率随机选择一个活跃节点。你能帮他估计更新次数的期望值吗？

为了避免精度问题，如果答案可以表示为不可约分数 $\frac{p}{q}$，则要求你报告满足 $qr \equiv p \pmod{998244353}$ 的最小非负整数 $r$。例如，$6 \times 166374072 \equiv 79 \pmod{998244353}$，$3 \times 332748131 \equiv 40 \pmod{998244353}$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例：

第一行包含一个整数 $n$。

接下来的 $n$ 行，每行包含两个整数 $u$ 和 $v$，表示第 $u$ 个节点和第 $v$ 个节点之间的一条边。

• $1 \le T \le 100$
• $3 \le n \le 10^5$
• $1 \le u < v \le n$
• 所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。
• 保证每个测试用例中的边各不相同，即不存在重边。

输出格式

对于每个测试用例，输出一行 "Case #x: y"（不含引号），其中 $x$ 是从 1 开始的测试用例编号，$y$ 是该测试用例的答案。

样例

输入 1

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

输出 1

Case #1: 166374072
Case #2: 332748131