Welcome to APLSPC!

As everyone knows, contest data is prepared on the night before the contest.

Unfortunately, while checking the data for a graph theory problem before NFLSPC, the Emperor discovered that the first two lines of all data files had been deleted by the evil Little P.

Looking at the incomplete data, the Emperor suddenly wondered how many ways there are to complete the first two lines such that the data is valid, modulo $998244353$.

Since the Emperor is the Emperor, he has given you the input file to solve this problem.

The Emperor, in his mercy, guarantees that at least one valid completion exists.

Given several lines of data, find how many input datasets exist such that:

• The dataset with the first two lines removed is equal to the given lines.
• The dataset fully satisfies the input format of the original problem.

The input format of the original problem is as follows:

The first line contains a positive integer $T$, followed by $T$ test cases.

The first line of each test case contains two positive integers $n, m$.

The next $m$ lines each contain two positive integers $u, v\ (1\leq u, v\leq n)$, describing a graph.

The graph may be disconnected and may contain multiple edges and self-loops.

The constraints of the original problem are:

$1\le T \leq 2\times 10^5 $;

$1\le n, m \leq 2\times 10^5$.

Input

Several lines (not exceeding $2\times 10^5$ lines), each containing two positive integers.

Output

A single line containing a positive integer representing the number of ways to complete the data, modulo $998244353$.

Examples

Input 1

2 1
1 1

Output 1

199999

Data Range

For all data: all input numbers are in the range $[1, 2\times 10^5]$, and the input contains no more than $2\times 10^5$ lines.