A. A Name of One's Own
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A new social network is launching, where $$$n$$$ people sign up one by one. The $$$i$$$-th person has two usernames in mind, $$$x_i$$$ and $$$y_i$$$ ($$$x_i \ne y_i$$$), and must register under exactly one of them. No two people may share a username.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, please count, modulo $$$998244353$$$, the number of ways to give each of the first $$$k$$$ people one of their two chosen usernames so that all $$$k$$$ chosen usernames are distinct.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of people.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$, $$$x_i \ne y_i$$$) — the two usernames person $$$i$$$ has in mind.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ space-separated integers; the $$$k$$$-th of them is the number of valid username assignments for the first $$$k$$$ people, taken modulo $$$998244353$$$.

Example
Input
4
1
1 2
2
1 2
3 4
8
7 1
7 3
7 9
2 5
5 8
2 8
8 6
10 1000000000
3
1 2
2 3
1 3
Output
2
2 4
2 3 4 8 12 8 8 16
2 3 2
Note

In the first test case, the single person may sign up as $$$1$$$ or $$$2$$$, so there are $$$2$$$ ways.

In the fourth test case, with only the first person there are $$$2$$$ ways. With the first two people, every combination works except both taking $$$2$$$, so there are $$$3$$$ ways. With all three people, out of the $$$8$$$ combinations only $$$(1, 2, 3)$$$ and $$$(2, 3, 1)$$$ leave no two people sharing a username, so there are $$$2$$$ ways.