moriartys-deceit

The evil mastermind, Moriarty, strikes again!  He sent Sherlock an image of a wall, with N integers painted on it. Sherlock is asked to solve the puzzle and find the next clue.
Sherlock knows that Moriarty is a deceitful person. All the numbers painted on the wall are not valid. Only the numbers that are Coprime with the integer X are valid, and the rest are a deceit. Help Sherlock find the valid integers from the given array A so that he can track down Moriarty.  

Input:
First line contains T. T test cases follow.
First line of each test case contains two space-separated integers N and X.
Second line of each test case contains N space-separated integers, forming the array A. 

Output:
Print the valid integers separated by spaces in the order that they appear in the list or "-1" (without the quotes) if there are no valid integers, in a new line for each test case.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^4
2 ≤ Ai, X ≤ 10^7

SAMPLE INPUT
1
5 4
2 5 8 3 13

SAMPLE OUTPUT
5 3 13

Difficulty: EASY

Starter code:

Solutions:
def gcda(a,b):
	while(b!=0):
		c=a%b
		a=b
		b=c
	return a
	


for _ in range(eval(input())):
	n,x=list(map(int,input().split()))
	arr=list(map(int,input().split()))
	count=0
	#print arr
	for it in arr:
		if gcda(it,x)==1:
			print(it, end=' ')
			
	print("")


from fractions import gcd

T = int(input())
for i in range(T):
	lis = list(map(int, input().split()))
	N = lis[0]
	#N = 5
	#X = 4
	X = lis[1]
	arr = list(map(int, input().split()))
	#arr = [2, 5, 8, 3, 13]
	result = []
	for i in arr:
	    if gcd(i, X) == 1:
	        result.append(i)
	    else:
	        continue
	if len(arr) > 0:
	    res = ""
	    for i in result:
	        res += str(i) + " "
	    print((res.lstrip()))
	else:
	    print("-1")


t=int(input())
for tc in range(t):
	n,x=list(map(int,input().split()))
	arr=list(map(int,input().split()))
	for i in arr:
		mx=max(i,x)
		Mx=mx
		mn=min(i,x)
		Mn=mn
		r=mx%mn
		while(r!=0):
			mx=mn
			mn=r
			r=mx%mn
		if(mn==1):
			print(i, end=' ')
	print() 


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, pow(a, 1, b))

def make_coprime_filter(X):
	def coprime_filter(A):
		return gcd(A, X) == 1
	return coprime_filter

T = int(input())
for i in range(T):
	_, X = list(map(int, input().split()))
	As = list(map(int, input().split()))
	co_filter = make_coprime_filter(X)
	r = list(filter(co_filter, As))
	print(" ".join(map(str, r)))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
def hcf(n1, n2):
	while n1*n2:
		if n1>n2:
			n1%=n2
		else:
			n2%=n1
	return max(n1, n2)

def coprime(n1,n2):
	return hcf(n1,n2) == 1
  
test_cases = int(input())

for i in range(0, test_cases):
    nx = input()
    n = nx.split()[0]
    x = int(nx.split()[1])
    arrstr = input()
    arr = [int(k.strip()) for k in arrstr.split()]
    res = []
    #print arr
    for j in arr:  
        if coprime(j, x):
            res.append(j)
    
    res = [str(r) for r in res]
    print(" ".join(res))
   




def gcd(a,b):
	if b==0: return a
	return gcd(b,a%b)
t=eval(input())
for _ in range(t):
	n,x=list(map(int,input().split()))
	a=list(map(int,input().split()))
	ans=""
	for i in range(n):
		if gcd(a[i],x)==1: ans+=str(a[i])+" "
	print(ans)


def egcd(a, b):
	x,y, u,v = 0,1, 1,0
	while a != 0:
		q, r = b//a, b%a
		m, n = x-u*q, y-v*q
		b,a, x,y, u,v = a,r, u,v, m,n
	gcd = b
	return gcd

t = int(input())

while t>0:
	lis = input().split()
	res = []
	n = int(lis[0])
	x = int(lis[1])
	elements = input().split()
	elements = list(map(int,elements))
	for i in elements:
	  gcd = egcd(x,i)
	  if gcd==1:
		res.append(i)
	for i in res:
	  print(i, end=' ')
	if len(res)==0:
	  print("-1")
	else:
	  print("")
	t = t-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import fractions
k=eval(input())
while(k>0):
	n,x=input().split(' ')
	n=int(n)
	x=int(x)
	string_input = input()
	arr = string_input.split(' ')
	arr = [int(a) for a in arr] 
	i=0
	c=0
	res=[]
	while(i<n):
		if fractions.gcd(arr[i],x) == 1:
			res.append(arr[i])
			c=c+1
		i=i+1
	if(c==0):
		print(-1)
	else:
		print(' '.join([str(item) for item in res]))
	k=k-1


from fractions import gcd

test= int(input())
for no in range(0,test):
	meas= list(map(int,input().split(" ")))
	mem= list(map(int,input().split(" ")))
	#print meas
	#print mem
	ans_list=[]
	for x in mem:
		if gcd(x,meas[1])==1:
			ans_list.append(str(x))
	if ans_list:
		print(' '.join(ans_list))
	else:
		print(-1)


tc=int(input())
from fractions import gcd
while tc>0:
	tc=tc-1
	N,X=list(map(int,input().split(' ')))
	A=list(map(int,input().split(' ')))
	flag=0
	for i in A:
		if gcd(i,X)==1:
			flag=1
			print(i, end=' ')
	
	if flag==0:
		print(-1)
	else:
		print()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def gcd(a,b) :
	if b == 0 :
		return a
	else :
		return gcd(b,a%b)


t = int(input())

while t>0 :
	t -= 1
	n,m = list(map(int, input().split()))
	s = []
	c=0
	ip1=list(map(int, input().split()))
	for i in range(0,n):
		if(gcd(ip1[i],m) == 1):
			s.append(ip1[i])
			c+=1
	if c==0 :
		print('-1')
	else :
		for i in range(0,c-1):
			print((s[i]), end=' ')
		print(s[c-1])	
		



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def gcd(a,b):
	while b:
		a, b = b, a%b
	
	return a
	

T=int(input())
if T <= 10:
	while T>0:
		NX= input()
		nx=NX.split()
		N=int(nx[0])
		X=int(nx[1])
		A=input();
		Array= [int(n) for n in A.split()]
		Ans=""
		for i in Array:
			if gcd(i,X)==1:
				Ans=Ans+str(i)+" "
		print(Ans)		
		T=T-1


def gcd(a,b):
	while(a!=0 and b!=0):
		if (a > b):
			a = a % b
		else:
			b = b % a
	if max(a,b) == 1:
		return True
	else:
		return False

t = int(input(''))
for i in range(0,t):
	my_str =(input(''))
	n,x = my_str.split()
	n = int(n)
	x= int(x)
   
	result =[]
	my_str =(input(''))
	ar = my_str.split()
	for j in range(0,len(ar)):
		ar[j] = int(ar[j])
		ans = gcd(max(x,ar[j]),min(x,ar[j]))
		if(ans==True):
			result.append(ar[j])

	my_str = ''
	for j in range(0,len(result)):
		my_str = my_str + str(result[j]) + ' '

	print(my_str)


from fractions import gcd
t=eval(input())

for j in range(0,t):
	a,b=input().split(" ")
	data=input().split(" ")
	a=int(a)
	b=int(b)
	answers=[]
	for i in range(0,a):
		if gcd(int(data[i]),b)==1:
			answers.append(data[i])
	print(" ".join(answers))


from fractions import gcd
for _ in range(eval(input())):
	n,x=list(map(int,input().split()))
	a=list(map(int,input().split()))
	s=""
	for i in range(n):
		if gcd(a[i],x)==1:
			s+=str(a[i])+" "
	print(s[:-1])
	


def gcd(a,b):
	while b:
		a,b=b,a%b
	return a

t=eval(input())
for i in range(0,t):
	s=input().split()
	r=''
	m,n=int(s[0]),int(s[1])
	a=input().split()
	for i in range(0,len(a)):
		a[i]=int(a[i])
	for i in a:
		x=gcd(i,n)
		
		if x==1:
			r=r+str(i)+" "
	print(r)

		


import math
import sys
from fractions import gcd
t=int(input())
for tt in range(t):
	a=(input()).split(' ')
	n=int(a[0])
	x=int(a[1])
	f=0
	an=input()
	bn=an.split(' ')
	for i in range(n):
		c=int(bn[i])
		if(gcd(c,x)==1):
			f=1
			print(c, end=' ')
	if(f==0):
		print(-1)
	else:
		print()
			


from fractions import gcd

T = int(input())
for i in range(T):
	lis = list(map(int, input().split()))
	N = lis[0]
	#N = 5
	#X = 4
	X = lis[1]
	arr = list(map(int, input().split()))
	#arr = [2, 5, 8, 3, 13]
	result = []
	for i in arr:
	    if gcd(i, X) == 1:
	        result.append(i)
	    else:
	        continue
	if len(arr) > 0:
	    res = ""
	    for i in result:
	        res += str(i) + " "
	    print((res.lstrip()))
	else:
	    print("-1")


import fractions

t=input()
t=(int)(t)
for i in range(t):
	x=[(int)(i) for i in input().split()]
	a,b=x[0],x[1]
	arr=[(int)(i) for i in input().split()]
	
	
	for j in range(len(arr)):
		if fractions.gcd(arr[j],b) is 1:
			print(arr[j], end=' ')
	print()


import sys
def gcd(a,b):
	if b==0:
		return a
	else:
		return gcd(b,a%b)
t = int(eval(input()))
while(t!=0):
    n,m = list(map(int,sys.stdin.readline().split()))
    a = list(map(int,sys.stdin.readline().split()))
    output = []
    flag = 0
    for i in a:
        if gcd(i,m)==1:
        	flag = 1
        	output.append(i)
    for i in output:
    	print(i, end=' ')
    if flag==1:
    	print("")
    else:
    	print("-1")
    t = t-1


from functools import reduce
def hcf(n1,n2):
	while n1*n2:
		if n1 > n2:
			n1 %= n2
		else:
			n2 %= n1
	return max( n1, n2 )

def coprime(n1,n2):
	return hcf(n1,n2) == 1

def checkCoPrimes(A,X):
	ls = [y for y in A if coprime(y,X)]
	if(ls == []):
		return '-1'
	else:
		return (reduce(lambda x,y: str(x) + ' ' + str(y),ls))

T = int(input())

ls = []

for i in range(0,T):
	nx = input()
	a = input()
	ls.append([nx,a])

for i in ls:
	nx1 = list(map(int,i[0].split()))
	N = nx1[0]
	X = nx1[1]
	A = list(map(int,i[1].split()))
	result = checkCoPrimes(A,X)
	print(result)