You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges.

You have to write a number on each vertex of the graph. Each number should be $1$, $2$ or $3$. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.

Calculate the number of possible ways to write numbers $1$, $2$ and $3$ on vertices so the graph becomes beautiful. Since this number may be large, print it modulo $998244353$.

Note that you have to write exactly one number on each vertex.

The graph does not have any self-loops or multiple edges.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^5$) — the number of tests in the input.

The first line of each test contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$) — the number of vertices and the number of edges, respectively. Next $m$ lines describe edges: $i$-th line contains two integers $u_i$, $ v_i$ ($1 \le u_i, v_i \le n; u_i \neq v_i$) — indices of vertices connected by $i$-th edge.

It is guaranteed that $\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$ and $\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$.


-----Output-----

For each test print one line, containing one integer — the number of possible ways to write numbers $1$, $2$, $3$ on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo $998244353$.


-----Example-----
Input
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
4
0



-----Note-----

Possible ways to distribute numbers in the first test:   the vertex $1$ should contain $1$, and $2$ should contain $2$;  the vertex $1$ should contain $3$, and $2$ should contain $2$;  the vertex $1$ should contain $2$, and $2$ should contain $1$;  the vertex $1$ should contain $2$, and $2$ should contain $3$. 

In the second test there is no way to distribute numbers.

Difficulty: interview

Starter code:

Solutions:
mod=998244353
import sys
input = sys.stdin.readline
from collections import deque
from collections import Counter


def calc(s,a):
    return (pow(2,s,mod)+pow(2,a-s,mod))%mod

 
def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))



testcase=int(input())
for test in range(testcase):
    n,m=list(map(int,input().split()))
    EDGE=[list(map(int,input().split())) for i in range(m)]
    EDGELIST=[[] for j in range(n+1)]
    ANS=1


    Group=[j for j in range(n+1)]

    for a,b in EDGE:
        Union(a,b)
        EDGELIST[a].append(b)
        EDGELIST[b].append(a)

    testing=[None]*(n+1)
    flag=1

    for i in range(1,n+1):
        if testing[i]!=None:
            continue

        score=1
        allscore=1

        testing[i]=1
        QUE = deque([i])
        while QUE:
            x=QUE.pop()
            for to in EDGELIST[x]:
                if testing[to]==-testing[x]:
                    continue
                if testing[to]==testing[x]:
                    flag=0
                    break
                testing[to]=-testing[x]
                if testing[to]==1:
                    score+=1
                allscore+=1
                QUE.append(to)
                
            if flag==0:
                break
        if flag==0:
            break
        #print(score,allscore)
        ANS=ANS*calc(score,allscore)%mod
    if flag==0:
        print(0)
        continue

    print(ANS)


from sys import stdin,stdout
for _ in range(int(input())):
    n,m=(int(x) for x in stdin.readline().split())
    a=[[] for i in range(n+1)]
    b=[]
    for i in range(m):
        c,d=(int(x) for x in stdin.readline().split())
        a[d].append(c)
        a[c].append(d)
        b.append([c,d])
    vis=[0]*(n+1)
    co=[]
    for i in range(1,n+1):
        if vis[i]==0:
            st=[i]
            vis[i]='e'
            e=1
            o=0
            while st:
                x=st.pop()
                for i in a[x]:
                    if vis[i]==0:
                        if vis[x]=='e':
                            vis[i]='o'
                            o+=1
                        else:
                            vis[i]='e'
                            e+=1
                        st.append(i)
            co.append([e,o])    
    fl=0
    for i in b:
        if vis[i[0]]==vis[i[1]]:
            stdout.write(str(0)+'\n')
            fl=1
            break
    if fl==0:
        k=[]
        for i in range(len(co)):
            x=co[i][0]
            y=co[i][1]
            m=1
            for i in range(x):
                m*=2
                m%=998244353
            ans=m
            m=1
            for i in range(y):
                m*=2
                m%=998244353
            ans+=m
            k.append(ans%998244353)
        ans=1
        for i in k:
            ans*=i
            ans%=998244353
        stdout.write(str(ans)+'\n')
        



''' Thruth can only be found at one place - THE CODE '''

''' Copyright 2018, SATYAM KUMAR'''
from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

printHeap = str()
memory_constrained = False
P = 10**9+7
import sys
sys.setrecursionlimit(10000000)

class Operation:
    def __init__(self, name, function, function_on_equal, neutral_value=0):
        self.name = name
        self.f = function
        self.f_on_equal = function_on_equal
def add_multiple(x, count):
    return x * count
def min_multiple(x, count):
    return x
def max_multiple(x, count):
    return x
sum_operation = Operation("sum", sum, add_multiple, 0)
min_operation = Operation("min", min, min_multiple, 1e9)
max_operation = Operation("max", max, max_multiple, -1e9)
class SegmentTree:
    def __init__(self,
                 array,
                 operations=[sum_operation, min_operation, max_operation]):
        self.array = array
        if type(operations) != list:
            raise TypeError("operations must be a list")
        self.operations = {}
        for op in operations:
            self.operations[op.name] = op
        self.root = SegmentTreeNode(0, len(array) - 1, self)
    def query(self, start, end, operation_name):
        if self.operations.get(operation_name) == None:
            raise Exception("This operation is not available")
        return self.root._query(start, end, self.operations[operation_name])
    def summary(self):
        return self.root.values
    def update(self, position, value):
        self.root._update(position, value)
    def update_range(self, start, end, value):
        self.root._update_range(start, end, value)
    def __repr__(self):
        return self.root.__repr__()
class SegmentTreeNode:
    def __init__(self, start, end, segment_tree):
        self.range = (start, end)
        self.parent_tree = segment_tree
        self.range_value = None
        self.values = {}
        self.left = None
        self.right = None
        if start == end:
            self._sync()
            return
        self.left = SegmentTreeNode(start, start + (end - start) // 2,
                                    segment_tree)
        self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end,
                                     segment_tree)
        self._sync()
    def _query(self, start, end, operation):
        if end < self.range[0] or start > self.range[1]:
            return None
        if start <= self.range[0] and self.range[1] <= end:
            return self.values[operation.name]
        self._push()
        left_res = self.left._query(start, end,
                                    operation) if self.left else None
        right_res = self.right._query(start, end,
                                      operation) if self.right else None
        if left_res is None:
            return right_res
        if right_res is None:
            return left_res
        return operation.f([left_res, right_res])
    def _update(self, position, value):
        if position < self.range[0] or position > self.range[1]:
            return
        if position == self.range[0] and self.range[1] == position:
            self.parent_tree.array[position] = value
            self._sync()
            return
        self._push()
        self.left._update(position, value)
        self.right._update(position, value)
        self._sync()
    def _update_range(self, start, end, value):
        if end < self.range[0] or start > self.range[1]:
            return
        if start <= self.range[0] and self.range[1] <= end:
            self.range_value = value
            self._sync()
            return
        self._push()
        self.left._update_range(start, end, value)
        self.right._update_range(start, end, value)
        self._sync()
    def _sync(self):
        if self.range[0] == self.range[1]:
            for op in self.parent_tree.operations.values():
                current_value = self.parent_tree.array[self.range[0]]
                if self.range_value is not None:
                    current_value = self.range_value
                self.values[op.name] = op.f([current_value])
        else:
            for op in self.parent_tree.operations.values():
                result = op.f(
                    [self.left.values[op.name], self.right.values[op.name]])
                if self.range_value is not None:
                    bound_length = self.range[1] - self.range[0] + 1
                    result = op.f_on_equal(self.range_value, bound_length)
                self.values[op.name] = result
    def _push(self):
        if self.range_value is None:
            return
        if self.left:
            self.left.range_value = self.range_value
            self.right.range_value = self.range_value
            self.left._sync()
            self.right._sync()
            self.range_value = None
    def __repr__(self):
        ans = "({}, {}): {}\n".format(self.range[0], self.range[1],
                                      self.values)
        if self.left:
            ans += self.left.__repr__()
        if self.right:
            ans += self.right.__repr__()
        return ans

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)
    
def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))

memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result


# -------------------------------------------------------------- MAIN PROGRAM
TestCases = True
testingMode = False
optimiseForReccursion = False #Can not be used clubbed with TestCases

def main():
    n,m = get_tuple()
    P=998244353
    neighbours = [[] for _ in range(n)]
    for i in range(m):
        a,b = get_tuple()
        neighbours[a-1].append(b-1)
        neighbours[b-1].append(a-1)
    nature = [0 for _ in range(n)] #0--> Unvisited, 1--> ODD, 2-> EVEN
    res = 1
    for k in range(0,n):
        if nature[k]!=0: continue
        curr_level = [k]
        nature[k] = 1
        r1,r2 = 2,1
        while len(curr_level)>0:
            next_level = []
            for curr_level_vertex in curr_level:
                curr_nature = nature[curr_level_vertex]
                for v in neighbours[curr_level_vertex]:
                    if nature[v]==0:
                        next_level.append(v)
                        nature[v] = 1 if curr_nature==2 else 2
                        if nature[v] ==1:
                            r1 = (r1*2)%P
                        else:
                            r2 = (r2*2)%P
                    else:
                        if nature[v]==curr_nature:
                            print(0)
                            return
            curr_level = next_level
        res = (res*(r1+r2)%P)%P
    r1,r2 = 1,1
    print(res)

# --------------------------------------------------------------------- END


if TestCases: 
    for _ in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

mod=998244353
from collections import deque
from sys import stdin,stdout
for _ in range(int(input())):
    n,m=list(map(int,stdin.readline().split()))
    a=[[] for i in range(n+1)]
    length=[0]*(n+1)
    if m==0:
        print(pow(3,n,mod))
    else:
        d=[]
        ans1=0;ans2=0;ans3=0;
        for __ in range(m):
            x,y=list(map(int,stdin.readline().split()))
            a[x].append(y)
            a[y].append(x)
        col=[0]*(n+1)
        de=deque([])
        for j in range(1,n+1):
            if len(a[j])==0:
                ans3+=1
            elif col[j]==0:
                col[j]=1
                de.append(j)
            #print(de)    
            c=1;c1=1
            while len(de):
                p=de.popleft()
                for i in a[p]:
                    if col[i]==0:
                        col[i]=-col[p]
                        de.append(i)
                        if col[i]==1:
                            c1+=1
                        c+=1            
            d.append([c,c1])
            
        flag=0
        for i in range(1,n+1):
            if flag==1:
                break
            for j in a[i]:
                if col[i]==col[j]:
                    flag=1
                    break
        #print(col)
        k=1
        if flag==1:
            stdout.write(str(0)+'\n')
        else:
            #print(d)
            for i in d:
                if i[0]!=1:
                    k1=pow(2,i[1],mod)
                    k1+=pow(2,i[0]-i[1],mod)
                    k*=k1
            k*=pow(3,ans3,mod)
            k%=mod
            stdout.write(str(k)+'\n')
            #print(ans1,ans2,ans3,flag)
            
                
                


#import resource
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**25)  # new thread will get stack of such size
def main():
    mod=998244353
    def ain():
        return list(map(int,sin().split()))
    def sin():
        return sys.stdin.readline().strip()
    """*********************************************************************************"""
    def dfs(x):
        if(p[x]==0):
            p[x]=1
            pt[0]+=1
            for i in de[x]:
                if(t[x]==1):
                    if(t[i]==1):
                        s[0]=0
                        return
                    else:
                        if(p[i]!=1):
                            t[i]=2
                            dfs(i)
                else:
                    if(t[i]==2):
                        s[0]=0
                        return
                    else:
                        if(p[i]!=1):
                            t[i]=1
                            r[0]+=1
                            dfs(i)
    h=[]
    pow1=[1]
    s=1
    for i in range(300000):
        s=(s*2)%mod
        pow1.append(s)
    for _ in range(int(input())):
        n,m=ain()
        de=[[] for i in range(n)]
        for i in range(m):
            x,y=ain()
            de[x-1].append(y-1)
            de[y-1].append(x-1)
        p=[0]*n
        s1=1
        t=[0]*n
        for i in range(n):
            if(p[i]==0):
                s=[1]
                pt=[0]
                t[i]=1
                r=[1]
                dfs(i)
                if(s[0]==1):
                    r1=pt[0]-r[0]
                    r2=r[0]
                    r1=(pow1[r1]+pow1[r2])%mod
                    s1=(s1*r1)%mod
                else:
                    s1=0
                    break
        h.append(str(s1))
    sys.stdout.write("\n".join(h))
threading.Thread(target=main).start()


import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**25)  # new thread will get stack of such size
def main():
    mod=998244353
    def ain():
        return list(map(int,sin().split()))
    def sin():
        return sys.stdin.readline().strip()
    """*********************************************************************************"""
    def dfs(x):
        if(p[x]==0):
            p[x]=1
            pt[0]+=1
            for i in de[x]:
                if(t[x]==1):
                    if(t[i]==1):
                        s[0]=0
                        return
                    else:
                        if(p[i]!=1):
                            t[i]=2
                            dfs(i)
                else:
                    if(t[i]==2):
                        s[0]=0
                        return
                    else:
                        if(p[i]!=1):
                            t[i]=1
                            r[0]+=1
                            dfs(i)
    h=[]
    pow1=[1]
    s=1
    for i in range(300000):
        s=(s*2)%mod
        pow1.append(s)
    for _ in range(int(input())):
        n,m=ain()
        de=[[] for i in range(n)]
        for i in range(m):
            x,y=ain()
            de[x-1].append(y-1)
            de[y-1].append(x-1)
        p=[0]*n
        s1=1
        t=[0]*n
        for i in range(n):
            if(p[i]==0):
                s=[1]
                pt=[0]
                t[i]=1
                r=[1]
                dfs(i)
                if(s[0]==1):
                    r1=pt[0]-r[0]
                    r2=r[0]
                    r1=(pow1[r1]+pow1[r2])%mod
                    s1=(s1*r1)%mod
                else:
                    s1=0
                    break
        h.append(str(s1))
    sys.stdout.write("\n".join(h))
threading.Thread(target=main).start()

from collections import deque
import time

anss = []
start = time.time()
t = int(input())

for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = list(map(int, input().split()))
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1

	for edge_count in range(m):
		u, v = list(map(int, input().split()))
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)

	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= 2 ** even + 2 ** odd
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part

				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= 3 ** factor
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)


from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

anss = []
t = int(input())

for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = map(int, input().split())
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1

	for edge_count in range(m):
		u, v = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)

	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part

				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)

from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

anss = []
t = int(input())

for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = map(int, input().split())
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1

	for edge_count in range(m):
		u, v = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)

	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part

				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)

# einlesen
# dfs für jede cc
#     Zählen, wie viele w/r
#     wenn cooring nicht möglich -> Ergebnis 0
#     sonst 2^w+2^r
M=998244353 
t=int(input())
n,m=0,0
g=[]
v=[]

def dfs(r):
    s=[r]
    v[r]=1
    c=[0,1]
    while s:
        x=s.pop()
        for j in g[x]:
            if v[j]==v[x]:return 0
            if v[j]==-1:
                v[j]=v[x]^1
                c[v[j]]+=1
                s.append(j)
    if c[0]==0 or c[1]==0:return 3
    return ((2**c[0])%M + (2**c[1])%M)%M

o=[]
for i in range(t):
    n,m=map(int,input().split())
    g=[[]for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    v=[-1]*n
    ox=1
    for j in range(n):
        if v[j]==-1:
            ox=(ox*dfs(j))%M
    o.append(ox)
print('\n'.join(map(str,o)))

from collections import defaultdict
import sys
#sys.setrecursionlimit(10**6)
#sys.stdin = open('E56D_input.txt', 'r')
#sys.stdout = open('output.txt', 'w')

input=sys.stdin.readline
#print=sys.stdout.write

graph = defaultdict(list)
color = [0] * ((3 * 10 ** 5) + 1000)
bipertite = True
MOD = 998244353
result = 1
color_count = [0] * 2
pow_value=[]
"""
def dfs(s, c):
    nonlocal color
    nonlocal bipertite
    nonlocal color_count

    color[s] = c
    color_count[c] += 1
    for i in range(0, len(graph[s])):

        if color[graph[s][i]] == -1:
            dfs(graph[s][i], 1-c)

        if color[s] == color[graph[s][i]]:
            bipertite = False

"""

t = int((input()))

#precomputing powers
pow_value.append(1)
for i in range(1,(3*10**5)+1000):
    next_value=(pow_value[i-1]*2)%MOD
    pow_value.append(next_value)
#------------------------


while t:
    n, m = list(map(int, input().split()))
    if m==0:
        print(pow(3,n,MOD))
        t-=1
        continue
    graph.clear()
    bipertite=True
    result=1

    for node in range(0,n+1):
        color[node]=-1
    while m:
        u, v = list(map(int, input().split()))
        graph[u].append(v)
        graph[v].append(u)
        m -= 1

    for i in range(1, n + 1):
        if (color[i] != -1):
            continue

        #bfs---
        bipertite = True
        color_count[0] = color_count[1] = 0
        queue=[]
        queue.append(i)
        color[i] = 0
        color_count[0] += 1
        while queue:
           # print(color_count[0],' ',color_count[1])
            if bipertite==False:
                break
            front_node=queue.pop()
            for child_node in range(0, len(graph[front_node])):

                if color[graph[front_node][child_node]] == -1:
                    color[graph[front_node][child_node]] = 1-color[front_node]
                    queue.append(graph[front_node][child_node])
                    color_count[color[graph[front_node][child_node]]] += 1


                elif color[front_node]==color[graph[front_node][child_node]]:
                    bipertite = False
                    break


        #bfs end
        if bipertite == False:
            print(0)
            break
        current=(pow_value[color_count[0]]+pow_value[color_count[1]])%MOD
        result = (result * current) % MOD

    if bipertite:
        print(result)
    t -= 1


from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

anss = []
t = int(input())

for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = map(int, input().split())
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1

	for edge_count in range(m):
		u, v = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)

	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part

				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)

from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write
 
anss = []
t = int(input())
 
for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = map(int, input().split())
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1
 
	for edge_count in range(m):
		u, v = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)
 
	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part
 
				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)

from collections import deque
from sys import stdin, stdout
input = stdin.readline

 
saida = []
t = int(input())
modulo = 998244353

for _ in range(t):
    ans = 1
    part = 0
    factor = 0
    queue = deque([])
    n, m = map(int, input().split())
    if m > (n // 2) * ( n // 2 + 1):
        saida.append('0')
        for edge_count in range(m):
            input()
        continue
    edge = [[] for i in range(n + 1)]
    visitados = [-1] * (n + 1)
    assure = 1
 
    for edge_count in range(m):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    visitados[1] = 0
    queue.append(1)
 
    break_all = False
    while not break_all:
        even, odd = 1, 0
        while queue and not break_all:
            search = queue.popleft()
            
            current = visitados[search]
            for i in edge[search]:
                if visitados[i] == -1:
                    visitados[i] = current ^ 1
                    if visitados[i] & 1:
                        odd += 1
                    else:
                        even += 1
                    queue.append(i)
                elif visitados[i] == current:
                    break_all = True
                else:
                    assert visitados[i] == current ^ 1
        if break_all:
            ans = 0
        else:
            if (even, odd) == (1, 0):
                factor += 1
            else:
                ans *= pow(2, even, modulo) + pow(2, odd, modulo)
                ans %= modulo
        while assure <= n:
            if visitados[assure] == -1:
                part += 1
                visitados[assure] = 2 * part
 
                queue.append(assure)
                break
            assure += 1
        if assure == n + 1:
            break
    ans *= pow(3, factor, modulo)
    ans %= modulo
    saida.append(str(ans))
print('\n'.join(saida))

from collections import deque
from sys import stdin, stdout
input = stdin.readline

 
saida = []
t = int(input())
modulo = 998244353

for _ in range(t):
    ans = 1
    part = 0
    factor = 0
    fila = deque([])
    n, m = map(int, input().split())

    if m > (n // 2) * ( n // 2 + 1):
        saida.append('0')
        for edge_count in range(m):
            input()
        continue
    edge = [[] for i in range(n + 1)]
    visitados = [-1] * (n + 1)
    assure = 1
 
    for arestas in range(m):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    visitados[1] = 0
    fila.append(1)
 
    break_all = False
    while not break_all:
        par, impar = 1, 0
        while fila and not break_all:
            search = fila.popleft()
            
            current = visitados[search]
            for i in edge[search]:
                if visitados[i] == -1:
                    visitados[i] = current ^ 1
                    if visitados[i] & 1:
                        impar += 1
                    else:
                        par += 1
                    fila.append(i)
                elif visitados[i] == current:
                    break_all = True
                else:
                    assert visitados[i] == current ^ 1
        if break_all:
            ans = 0
        else:
            if (par, impar) == (1, 0):
                factor += 1
            else:
                ans *= pow(2, par, modulo) + pow(2, impar, modulo)
                ans %= modulo
        while assure <= n:
            if visitados[assure] == -1:
                part += 1
                visitados[assure] = 2 * part
 
                fila.append(assure)
                break
            assure += 1
        if assure == n + 1:
            break
    ans *= pow(3, factor, modulo)
    ans %= modulo
    saida.append(str(ans))
print('\n'.join(saida))

from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write
 
anss = []
t = int(input())
 
for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	n, m = map(int, input().split())
	if m > (n // 2) * ( n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1
 
	for edge_count in range(m):
		u, v = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)
 
	break_all = False
	while not break_all:
		even, odd = 1, 0
		while queue and not break_all:
			search = queue.popleft()
			# print('searching vertex {0}, {1}'.format(search, edge[search]))
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		# print(flag)
		if break_all:
			# print('break_all')
			ans = 0
		else:
			if (even, odd) == (1, 0):
				factor += 1
			else:
				ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
				ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part
 
				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))
# print(time.time() - start)

import sys
input = sys.stdin.readline
from collections import deque

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

def bfs(s):
    q = deque([s])
    color[s] = 1
    b, w = 1, 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
                
                if color[nv]==1:
                    b += 1
                else:
                    w += 1
            else:
                if color[nv]==color[v]:
                    return -1, -1
    
    return b, w

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    adj_list = [[] for _ in range(n)]
    uf = Unionfind(n)
    MOD = 998244353
    
    for _ in range(m):
        u, v = map(int, input().split())
        adj_list[u-1].append(v-1)
        adj_list[v-1].append(u-1)
        uf.unite(u-1, v-1)
    
    roots = set(uf.root(i) for i in range(n))
    ans = 1
    color = [0]*n
    
    for r in roots:
        if uf.count(r)==1:
            ans *= 3
        else:
            b, w = bfs(r)
            
            if b==-1:
                ans = 0
                break
            else:
                ans *= pow(2, b, MOD)+pow(2, w, MOD)
        
        ans %= MOD
    
    print(ans)

import sys
input=sys.stdin.readline
#from math import *
#sys.setrecursionlimit(10**6)
from collections import deque
mod=998244353
t=int(input())
def isbip2(i,vis,col,f):
    q=deque()
    q.append(i)
    vis[i]=1
    col[i]=0
    f[0]+=1
    while len(q)>0:
        z=q.popleft()
        for j in a[z]:
            if col[z]==col[j]:
                return 0
            if vis[j]==0:
                vis[j]=1
                col[j]=col[z]^1
                f[col[j]]+=1
                q.append(j)
    return 1  

def isbip(col,vis,n):
    c=1
    z=0;o=0
    f=[0,0]
    for i in range(1,n+1):
        if vis[i]:
            continue
        if not isbip2(i,vis,col,f):
            return 0
        c=  (c%mod*(pow(2,f[0]-z,mod)+pow(2,f[1]-o,mod)))%mod 

        z=f[0]
        o=f[1]
    return c    
    
while t>0:
    t-=1
    n,m=list(map(int,input().split()))
    col=[-1 for i in range(n+1)]
    a=[[] for i in range(n+1)]
    vis=[0 for i in range(n+1)]
    for i in range(m):
        x,y=list(map(int,input().split()))
        a[x].append(y)
        a[y].append(x)
    print(isbip(col,vis,n))


from sys import stdin,stdout
from collections import defaultdict
import sys, threading
sys.setrecursionlimit(122500) # max depth of recursion
threading.stack_size(2**25)
def main():
    def power(x, p):
        re = 1
        mode= 998244353
        while p:
            if p & 1:
                re = re * x % mode
            x = x * x % mode
            p >>= 1
        return re;

    def dfs(node,col):
        visited[node]=True
        c[col]+=1
        color[node]=col
        for j in dic[node]:
            if not visited[j]:
                if not dfs(j, col ^ 1):
                    return False
            else:
                if color[j]==color[node]:
                    return False
        return True


    t=int(stdin.readline())
    for _ in range(t):
        mod=998244353
        n,m=list(map(int,stdin.readline().split()))
        dic=defaultdict(list)
        for i in range(m):
            u,v=list(map(int,stdin.readline().split()))
            dic[u].append(v)
            dic[v].append(u)
        visited=[False]*(n+1)
        color=[-1]*(n+1)
        c=[0]*2
        result=1
        flag=0
        #print(dic)
        for i in range(1,n+1):
            if not visited[i]:
                res=dfs(i,0)
                if not res:
                    flag=1
                    break
                else:
                    result=(result*(power(2,c[0])+power(2,c[1])))%mod
                    c[0]=0
                    c[1]=0
        if flag==1:
            stdout.write("0\n")
        else:
            stdout.write(str(result)+"\n")
threading.Thread(target=main).start()





from sys import stdin,stdout
from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**25)
def main():
    def power(x, p):
        re = 1
        mode= 998244353
        while p:
            if p & 1:
                re = re * x % mode
            x = x * x % mode
            p >>= 1
        return re;

    def dfs(node,col):
        visited[node]=True
        c[col]+=1
        color[node]=col
        for j in dic[node]:
            if not visited[j]:
                if not dfs(j, col ^ 1):
                    return False
            else:
                if color[j]==color[node]:
                    return False
        return True


    t=int(stdin.readline())
    for _ in range(t):
        mod=998244353
        n,m=list(map(int,stdin.readline().split()))
        dic=defaultdict(list)
        for i in range(m):
            u,v=list(map(int,stdin.readline().split()))
            dic[u].append(v)
            dic[v].append(u)
        visited=[False]*(n+1)
        color=[-1]*(n+1)
        c=[0]*2
        result=1
        flag=0
        #print(dic)
        for i in range(1,n+1):
            if not visited[i]:
                res=dfs(i,0)
                if not res:
                    flag=1
                    break
                else:
                    result=(result*(power(2,c[0])+power(2,c[1])))%mod
                    c[0]=0
                    c[1]=0
        if flag==1:
            stdout.write("0\n")
        else:
            stdout.write(str(result)+"\n")
threading.Thread(target=main).start()





from sys import stdin,stdout
from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10**5) # max depth of recursion
threading.stack_size(2**25)
def main():
    def power(x, p):
        re = 1
        mode= 998244353
        while p:
            if p & 1:
                re = re * x % mode
            x = x * x % mode
            p >>= 1
        return re;

    def dfs(node,col):
        visited[node]=True
        c[col]+=1
        color[node]=col
        for j in dic[node]:
            if not visited[j]:
                if not dfs(j, col ^ 1):
                    return False
            else:
                if color[j]==color[node]:
                    return False
        return True


    t=int(stdin.readline())
    for _ in range(t):
        mod=998244353
        n,m=list(map(int,stdin.readline().split()))
        dic=defaultdict(list)
        for i in range(m):
            u,v=list(map(int,stdin.readline().split()))
            dic[u].append(v)
            dic[v].append(u)
        visited=[False]*(n+1)
        color=[-1]*(n+1)
        c=[0]*2
        result=1
        flag=0
        #print(dic)
        for i in range(1,n+1):
            if not visited[i]:
                res=dfs(i,0)
                if not res:
                    flag=1
                    break
                else:
                    result=(result*(power(2,c[0])+power(2,c[1])))%mod
                    c[0]=0
                    c[1]=0
        if flag==1:
            stdout.write("0\n")
        else:
            stdout.write(str(result)+"\n")
threading.Thread(target=main).start()





from sys import stdin,stdout
from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10**5) # max depth of recursion
threading.stack_size(2**25)
def main():
    def power(x, p):
        re = 1
        mode= 998244353
        while p:
            if p & 1:
                
                re = re * x % mode
            x = x * x % mode
            p >>= 1
        return re;

    def dfs(node,col):
        visited[node]=True
        c[col]+=1
        color[node]=col
        for j in dic[node]:
            if not visited[j]:
                if not dfs(j, col ^ 1):
                    return False
            else:
                if color[j]==color[node]:
                    return False
        return True


    t=int(stdin.readline())
    for _ in range(t):
        mod=998244353
        n,m=list(map(int,stdin.readline().split()))
        dic=defaultdict(list)
        for i in range(m):
            u,v=list(map(int,stdin.readline().split()))
            dic[u].append(v)
            dic[v].append(u)
        visited=[False]*(n+1)
        color=[-1]*(n+1)
        c=[0]*2
        result=1
        flag=0
        #print(dic)
        for i in range(1,n+1):
            if not visited[i]:
                res=dfs(i,0)
                if not res:
                    flag=1
                    break
                else:
                    result=(result*(power(2,c[0])+power(2,c[1])))%mod
                    c[0]=0
                    c[1]=0
        if flag==1:
            stdout.write("0\n")
        else:
            stdout.write(str(result)+"\n")
threading.Thread(target=main).start()





import sys
from collections import defaultdict,deque
mod=998244353
def get(graph):
    vis=defaultdict(int)
    l=[]
    for i in range(1,n+1):
        if vis[i]==0:
            vis[i]=1
            q=deque()
            q.append(i)
            even=0
            odd=0
            while q:
                a=q.popleft()
                if vis[a]&1:
                    odd+=1
                else:
                    even+=1
                for x in graph[a]:
                    if vis[x]==0:
                        if vis[a]==1:
                            vis[x]=2
                        else:
                            vis[x]=1
                        q.append(x)
                    else:
                        if vis[x]==vis[a]:
                            return 0
            l.append([even,odd])
    m=len(l)
    x=pow(2,l[0][0],mod)
    y=pow(2,l[0][1],mod)
    ans=(x+y)%mod
    for i in range(1,m):
        x=pow(2,l[i][0],mod)
        y=pow(2,l[i][1],mod)
        z=(x+y)%mod
        ans=ans*z
        ans%=mod
    return ans%mod
    return False
'''def count(graph):
    vis=defaultdict(int)
    even=0
    odd=0
    for i in range(1,n+1):
        if vis[i]==0:
            vis[i]=1
            q=deque()
            q.append([i,0])
            while q:
                a,dis=q.popleft()
                if dis%2==0:
                    even+=1
                else:
                    odd+=1
                for x in graph[a]:
                    if vis[x]==0:
                        vis[x]=1
                        q.append([x,dis+1])
    return (even,odd)'''
t=int(sys.stdin.readline())
for _ in range(t):
    graph=defaultdict(list)
    
    n,m=list(map(int,sys.stdin.readline().split()))
    for i in range(m):
        u,v=list(map(int,sys.stdin.readline().split()))
        graph[u].append(v)
        graph[v].append(u)
    '''if _ == 5:
        print(graph)
    #print(graph,'graph')'''
    z=get(graph)
    #print(z,'z')
    print(z)


import sys
from collections import defaultdict,deque
mod=998244353
def get(graph):
    vis=defaultdict(int)
    l=[]
    for i in range(1,n+1):
        if vis[i]==0:
            vis[i]=1
            q=deque()
            q.append(i)
            even=0
            odd=0
            while q:
                a=q.popleft()
                if vis[a]&1:
                    odd+=1
                else:
                    even+=1
                for x in graph[a]:
                    if vis[x]==0:
                        if vis[a]==1:
                            vis[x]=2
                        else:
                            vis[x]=1
                        q.append(x)
                    else:
                        if vis[x]==vis[a]:
                            return 0
            l.append([even,odd])
    m=len(l)
    x=pow(2,l[0][0],mod)
    y=pow(2,l[0][1],mod)
    ans=(x+y)%mod
    for i in range(1,m):
        x=pow(2,l[i][0],mod)
        y=pow(2,l[i][1],mod)
        z=(x+y)%mod
        ans=ans*z
        ans%=mod
    return ans%mod
t=int(sys.stdin.readline())
for _ in range(t):
    graph=defaultdict(list)
    
    n,m=list(map(int,sys.stdin.readline().split()))
    for i in range(m):
        u,v=list(map(int,sys.stdin.readline().split()))
        graph[u].append(v)
        graph[v].append(u)
    
    z=get(graph)
    print(z)


# Not my code
# https://codeforces.com/contest/1093/submission/80633286

# Template: https://codeforces.com/profile/kabeer27
from __future__ import division, print_function

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc


mod = 998244353
def power(base, exp):
    base %= mod
    if exp < 3:
        return (base**exp) % mod
    half = power(base*base, exp//2)
    return (half*base) % mod if exp % 2 == 1 else half % mod
 
 
def solve():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    count, visited = [0, 0], [-1 for _ in range(n+1)]
 
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    possible, ans = True, 1
 
    @bootstrap
    def dfs(node, par, parity):
        nonlocal possible, visited, graph, count
        if visited[node] != -1:
            possible = False if visited[node] != parity else possible
            yield None
        visited[node] = parity
        count[parity] += 1
        for child in graph[node]:
            if child != par:
                yield dfs(child, node, 1-parity)
        yield
 
    # check for each node and update the answer
    for i in range(1, n+1):
        if visited[i] == -1:
            count = [0, 0]
            dfs(i, -1, 1)
            ans *= (power(2, count[0]) + power(2, count[1])) % mod
            ans %= mod
 
    # print(ans if possible else 0)
    sys.stdout.write(str(ans) if possible else '0')
    sys.stdout.write('\n')
 
def main():
    tests = 1
    tests = int(input().strip())
    for test in range(tests):
        solve()
 
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

main()