Solicitation of Murder

問題文

牢屋敷に $N$ 人の囚人がいます。各囚人にはそれぞれ $1$ から $N$ までの番号が付けられており、はじめすべての囚人は生存しています。

$M$ 個の関係が整数対 $(A_i, B_i) ~ (1 \le i \le M)$ として与えられます。 $i$ 番目の関係は「囚人 $A_i$ は囚人 $B_i$ に対して殺意を持っている」というものです。

これから牢屋敷では、以下の手続きで殺人事件が発生します。

• 以下の操作を $0$ 回以上の自由な回数繰り返す。
  • $2$ 人の生存している囚人 $a, b$ であって、囚人 $a$ が囚人 $b$ に対して殺意を持っているものを一つ選ぶ。囚人 $b$ を殺害し、生存していない状態にする。

殺人事件が発生した後における生存している囚人の集合としてあり得るものの個数を素数 $998244353$ で割った余りを求めてください。

$2$ つの「生存している囚人の集合」は、ある囚人が一方の集合では生存しており、他方では生存していないとき（かつそのときに限り）区別します。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• すべてのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• すべてのテストケースにおける $M$ の総和は $2 \times 10^5$ 以下
• $1 \le A_i, B_i \le N$
• $A_i \ne B_i$
• $i \ne i'$ ならば $(A_i, B_i) \ne (A_{i'}, B_{i'})$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

サンプル 1

入力

3
3 2
1 2
1 3
13 0
4 5
1 2
3 1
2 3
2 4
1 4

出力

4
1
14

$1$ 番目のテストケースについて、殺人事件が発生した後の囚人の集合としてあり得るものは $\{1\}, ~ \{1, 2\}, ~ \{1, 3\}, ~ \{1, 2, 3\}$ の $4$ 個です。