memories-1

N coders decided to go for a trip for the upcoming weekend. They chose Crater Lake National Park in Oregon, USA as their destination, because they all like to take a lot of photos and the beautiful nature gives them a chance to do so.

In order to capture some memories from the trip, they wanted to take the greatest number of distinct meaningful photos from their trip. Since they all are math geeks, they consider two photos different if and only if the sets of coders on both photos are different. Moreover, they consider a photo meaningful if and only if there is at least one coder on the photo.

However, not all coders like each other. In more detail, there are P pairs of coders who don't like each other very much, so they don't want to appear together on any photo, otherwise the whole trip will be ruined!

Your task, as you obviously take part in the trip, is to calculate the maximum number of distinct meaningful photos that can be taken in such a way that the trip will not be ruined.

Input format:

In the first line, there is a single integer T denoting the number of test cases to handle. Then, description of T tests follow. In the first line of each such description, two integers N and P are given. Then P lines follow, each one consisting of two distinct integers A and B denoting a single pair of coders who don't like each other.

Output format:

Output exactly T lines, and in the i^th of them, print a single integer denoting the answer to the i^th test case.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 15
1 ≤ P ≤ N * (N-1) / 2
1 ≤ A, B ≤ N 
A ≠ B 
All pairs of coders given in a single test are distinct.

SAMPLE INPUT
1
3 1
1 2

SAMPLE OUTPUT
5

Explanation

In the only test case, there are N = 3 coders and one pair of coders who don't like each other. The maximal number of photos the coders can take is 5, and the following sets of coders can appear on a single photo: {1}, {2}, {3}, {1, 3}, {2,3}.

Source: hackerearth | Difficulty: EASY
Tags: Bit manipulation


Solutions:
t = eval(input())
for test in range(t):
	n,p = list(map(int,input().split()))
	invalid = []
	for pair in range(p):
		s = ['0']*n
		a,b = list(map(int,input().split()))
		s[a-1],s[b-1] = '1','1'
		invalid.append(int(''.join(s),base=2))

	ans = 0
	lt = 2**n
	for poss in range(1,lt):
		ve = ['0']*n
		for j in range(n):
			if(poss & (1<<j)):
				ve[j] = '1'
		ch = int(''.join(ve),base=2)
		ok = True
		for no in invalid:
			if(no&ch==no):
				ok = False
		if ok:
			ans+=1
	print(ans)


import sys
import operator
import copy

def makeImage(i,N):
	arr = []
	
	element = 1
	while(i):
		if i%2 == 1:
			arr.append(element)
		i/=2
		element+=1
	return arr

T = eval(input())
for _ in range(T):
	N,P = list(map(int,input().strip().split(' ')))

	pairs = []

	for _ in range(P):
		A,B = list(map(int, input().strip().split(' ')))
		pairs.append((A,B))

	Range = 2**N
	count = 0
	for i in range(1,Range):
		image = makeImage(i,N)
		
		correctImage = True
		
		for p in pairs:
			if p[0] in image and p[1] in image:
				correctImage = False
				break
		if correctImage:
			count+=1
	print(count)


















'''
https://www.hackerearth.com/algorithms-qualifiers-round-3/algorithm/memories-1/
'''

T = int(eval(input()))

for tc in range(T):
	N,P = [int(x) for x in input().split()]
	# This is for the case when every two pair is non-overlapping as usual
	# print(2**N - 1 - 2**(N-2*P) * (2**P - 1))
	num_list = []
	for x in range(P):
		A,B = [int(x) for x in input().split()]
		num_list.append(2**(A-1) + 2**(B-1))
	# print('num_list = {}'.format(num_list))
	count = 0
	N_list = range(1,2**N+1)
	# print('N_list={}'.format(N_list))
	for n in N_list :
		if len([x for x in num_list if x & n == x]) > 0 :
			count += 1

	print((2**N -1 - count))



from itertools import combinations, chain
allsubsets = lambda n: list(chain(*[combinations(list(range(n)), ni) for ni in range(n+1)]))
t=int(input())
while t:
	hash=[0]*(2**15)
	n,p=list(map(int,input().split()))
	sub=allsubsets(n)
	ans=0
	while p:
		a,b=list(map(int,input().split()))
		for i in range(len(sub)):
			x=sub[i]
			if a-1 in x and b-1 in x and hash[i]==0:
				hash[i]=1
				ans+=1
		p-=1
	print((2**n)-ans-1)
	t-=1



for i in range(eval(input())):
	n,p = list(map(int,input().split()))
	d = {}
	for j in range(p):
		a,b = list(map(int,input().split()))
		a -= 1
		b -= 1
		d[tuple([a,b])] = 1
		d[tuple([b,a])] =1
	ctr = 0
	for q in range(1,2**n):
		st = bin(q)[2:]
		st = '0'*(n-len(st)) + st
		fl = True
		for x in range(n):
			for y in range(x+1,n):
				if st[x]=='1' and st[y]=='1':
					try:
						if d[(x,y)]:
							fl = False
							break
					except:
						pass
		if fl:
			ctr += 1
			#print st
	print(ctr)