루프와 다중 간선이 없는 무향 그래프가 주어집니다. 각 정점에 연결된 간선들의 가중치 합이 5의 배수(즉, 어떤 정수 $k$에 대하여 $5k$와 같음)가 되도록 간선에 $[0; 4]$ 범위의 정수를 적는 방법의 수를 구하세요.

정답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 구하면 됩니다.

입력

첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 500\,000$)가 주어집니다.

다음 줄부터는 $t$개의 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 정점의 수 $n$과 간선의 수 $m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$)이 주어집니다.

다음 $m$개의 줄에는 간선에 대한 설명이 주어지며, $i$번째 줄에는 그래프에서 정점 $a_i$와 $b_i$를 연결하는 간선을 나타내는 두 정수 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)가 주어집니다.

다중 간선은 존재하지 않음이 보장됩니다.

또한 모든 테스트 케이스에 대한 $n + m$의 총합은 최대 $500\,000$임이 보장됩니다.

출력

각 테스트 케이스마다, 각 정점에 연결된 간선들의 가중치 합이 5의 배수가 되도록 간선에 $[0; 4]$ 범위의 정수를 적는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 출력하세요.

예제

입력 1

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

출력 1

1
1
5