Quantum love solving mathematical problems. One day his teacher give him problem on divisibility to check his mathematical skills. He give him four numbers a,b,c,d and asked him to check whether (a^b) is divisible by (c^d) or not. As the constrains are high, so quantum need your help to answer the query.

INPUT

First line of Input contains no. of test cases T.
Each test case contain four numbers a,b,c,d.

OUTPUT

For each test case print "Divisible" if they are divisible and "Not divisible" if they are not divisible (without quotes).

CONSTRAINTS

T ≤ 50

1 ≤ a,b,c ≤10^9

0 ≤ d ≤10^9

SAMPLE INPUT
1
4 6 2 4

SAMPLE OUTPUT
Divisible
P=[1]*100001
p=[]
for i in range(2,100001):
	if P[i]:
		p.append(i)
		for j in range(i<<1,100001,i):
			P[j]=0

for t in range(input()):
	a,b,c,d=map(int,raw_input().split())
	ap=[]
	ae=[]
	cp=[]
	ce=[]

	if d==0:
		print "Divisible"
		continue

	for x in p:
		if a%x==0:
			cnt=0
			while a%x==0: 
				a/=x
				cnt+=1
			ap.append(x)
			ae.append(cnt*b)
	if a>1:
		ap.append(a)
		ae.append(b)

	for x in p:
		if c%x==0:
			cnt=0
			while c%x==0: 
				c/=x
				cnt+=1
			cp.append(x)
			ce.append(cnt*d)
	if c>1:
		cp.append(c)
		ce.append(d)

	f=1
	for i in range(len(cp)):
		if cp[i] not in ap:
			f=0
			break
		if ce[i]>ae[ap.index(cp[i])]:
			f=0
			break

	print "Divisible" if f else "Not divisible"