你有一个凸 $n$ 边形，并画了 $n-3$ 条不在多边形内部相交的对角线，将 $n$ 边形划分成了 $n-2$ 个三角形。这可以被看成一张 $n$ 个结点 $2n-3$ 条无向边的图。

你需要对于每条对角线计算，删除该对角线后，这张图有多少个生成树。

输入格式

输入的第一行有一个正整数 $n$（$4\leq n\leq 5\times 10^5$），表示多边形的边数。

之后有 $n-3$ 行，每行输入两个正整数 $u_i,v_i$（保证 $1\leq u_i,v_i\leq n$，且这是一条对角线），表示一条对角线的两个端点。

输出格式

输出 $n-3$ 行，每行一个自然数，第 $i$ 行的自然数表示删去对角线 $(u_i,v_i)$ 后原图的最小生成树个数。

由于结果可能过大，上述答案只需要输出对 $998244353$ 求余的结果即可。

样例

输入

6
1 4
1 3
1 5

输出

30
29
29