greatest-dumpling-fight

Gaurav and Aayush are participating in the Tekken Tag Tournament of 20123. Of course, Dr. Sudarshan Iyengar has formed the rules of the fight.

There is a long horizontal line of infinite length with a center point P. Initially both Gaurav and Aayush will stand on the center P of the line facing each other. Don't worry, the line is thick enough to hold Aayush and Gaurav at the same place and at the same time. Gaurav can jump either A or B units to the left or right in one move. Aayush can jump either C or D units to the left or right in one move.

Dr. Sudarshan Iyengar wants to place exactly one "Health Potion" on the line such that both Gaurav and Aayush will be able to reach it independently in one or more moves. Also the "Health Potion" can be placed at most K units away from the center of the rope. Dr. Sudarshan Iyengar will let you watch the fight if you can decide the number of possible positions on the line to place the "Health Potion".

Input

First line contains T, the number of test cases. Each of the next T lines contains five positive integers, A B C D K.

1 ≤ T ≤ 1000 

1 ≤ A,B,C,D,K ≤ 10^18

Output

For each test case, output on a newline, the number of possible positions to place the "Health Potion" on the line.

Example

Input:

3

2 4 3 6 7

1 2 4 5 1

10 12 3 9 16

Output:

3

3

5

Explanation:

For the second case,

Aayush jumps 2 units to the right and then 1 unit to the left.
  Gaurav jumps 5 units to the right and then 4 units to the left 
to reach 1 unit right from the center.

Aayush jumps 2 units to the left and then 1 unit to the right.
  Gaurav jumps 5 units to the left and then 4 units to the right 
to reach 1 unit left from the center.

"Health Potion" can also be placed at the center as players  can reach it in 2 moves.
Thus, there are three different positions at most 1 unit away from the center 
that are reachable by both the players in one or more moves.

SAMPLE INPUT
3
2 4 3 6 7
1 2 4 5 1
10 12 3 9 16

SAMPLE OUTPUT
3
3
5

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


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

def LCM(a,b):
	return (a*b)/HCF(a,b)

def space2list(S):
	slist=[]
	temp=""
	for i in S:
		if i==" ":
			slist.append(int(temp))
			temp=""
		else:
			temp=temp+i
	if temp!="":
		slist.append(int(temp))
	return slist

testcases=int(input())
i=0
while (i<testcases):
	data=space2list(input())
	hcf1=HCF(data[0],data[1])
	hcf2=HCF(data[2],data[3])
	lcm=LCM(hcf1,hcf2)
	n=int(data[4]/lcm)
	print(2*n+1)
	i=i+1