Lunar phụ trách phát thẻ cho các tình nguyện viên đến trực tại đài quan sát. Có ~n~ người xếp hàng nhận thẻ. Người thứ ~i~ mang theo hai mã thẻ đã chọn trước là ~x_i~ và ~y_i~. Lunar phải cấp cho người đó đúng một trong hai mã. Mỗi mã chỉ được cấp cho tối đa một người trong cùng một ca trực.

Lunar muốn biết với mỗi ~k~ từ ~1~ đến ~n~, có bao nhiêu cách cấp thẻ cho đúng ~k~ người đầu hàng sao cho các mã được cấp đôi một khác nhau. Khi xét một giá trị ~k~ mới, Lunar được chọn lại mã cho tất cả ~k~ người. Hai cách cấp thẻ khác nhau nếu có ít nhất một người nhận mã khác nhau giữa hai cách đó.

Hãy tính số cách cấp thẻ cho từng giá trị ~k~, lấy phần dư theo ~998244353~.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số bộ test ~(1 \le t \le 10^4)~.
• Dòng đầu tiên của mỗi bộ test chứa số nguyên ~n~ là số người ~(1 \le n \le 3 \cdot 10^5)~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~x_i~ và ~y_i~ là hai mã của người thứ ~i~ ~(1 \le x_i, y_i \le 10^9,\ x_i \ne y_i)~. Nhiều người có thể đưa ra cùng một cặp mã.

Đảm bảo tổng ~n~ của tất cả các bộ test trong một file input không vượt quá ~3 \cdot 10^5~.

Output

Với mỗi bộ test, in một dòng gồm ~n~ số nguyên cách nhau bởi dấu cách. Số thứ ~k~ là số cách cấp thẻ hợp lệ cho ~k~ người đầu hàng, lấy phần dư theo ~998244353~.

Subtask

Sample Input 1

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

Sample Output 1

2
2 4
2 3 2

Giải thích

• Với test 1 Người duy nhất có thể nhận mã ~1~ hoặc ~2~, nên có ~2~ cách.
• Với test 2. Khi chỉ xét người đầu tiên, có ~2~ cách. Người thứ hai chọn giữa mã ~3~ và ~4~, đều khác hai mã của người đầu tiên, nên khi xét cả hai người có ~2 \cdot 2 = 4~ cách.