Chef Shifu and Chef Po are participating in the Greatest Dumpling Fight of 2012.
Of course, Masterchef Oogway has formed the rules of the fight.

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

Masterchef Oogway wants to place exactly one dumpling on the rope such that
both Chef Shifu and Chef Po will be able to reach it independently in one or more moves.
Also the dumpling can be placed at most K units away from the center of the rope.
Masterchef Oogway will let you watch the fight if you can decide the number of possible positions on the rope to place the dumpling. 

------ 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 dumpling on the rope. 

----- Sample Input 1 ------ 
3
2 4 3 6 7
1 2 4 5 1
10 12 3 9 16
----- Sample Output 1 ------ 
3
3
5
----- explanation 1 ------ 
For the second case,

Chef Po jumps 2 units to the right and then 1 unit to the left.
Chef Shifu jumps 5 units to the right and then 4 units to the left 
to reach 1 unit right from the center.

Chef Po jumps 2 units to the left and then 1 unit to the right.
Chef Shifu jumps 5 units to the left and then 4 units to the right 
to reach 1 unit left from the center.

Dumpling can also be placed at the center as a chef 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 chefs in one or more moves.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

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

def lcm(a, b):
	return a // gcd(a, b) * b
T = int(input())
for i in range(T):
	str = input().split()
	a = int(str[0])
	b = int(str[1])
	c = int(str[2])
	d = int(str[3])
	k = int(str[4])
	ans = lcm(gcd(a, b), gcd(c, d))
	ans = k // ans
	ans = 2 * ans + 1
	print(ans)


from math import gcd
import sys
for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	g = gcd(a, b)
	f = gcd(c, d)
	print(2 * (k // (g * f // gcd(g, f))) + 1)


import math
for _ in range(int(input())):
	(a, b, c, d, k) = map(int, input().split())
	g1 = math.gcd(a, b)
	g2 = math.gcd(c, d)
	g = math.gcd(g1, g2)
	m = g1 * g2 // g
	temp = k // m
	print(temp * 2 + 1)


import math
t = int(input())
for _ in range(t):
	(a, b, c, d, k) = map(int, input().split())
	x = math.gcd(a, b)
	y = math.gcd(c, d)
	z = x * y // math.gcd(x, y)
	ans = k // z
	print(2 * ans + 1)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for i in range(int(input())):
	(a, b, c, d, k) = [int(x) for x in input().split()]
	g1 = gcd(a, b)
	g2 = gcd(c, d)
	lcm = g1 * g2 // gcd(g1, g2)
	ans = 2 * (k // lcm) + 1
	print(ans)


def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	(a, b, c, d, k) = map(int, input().split())
	gcd1 = gcd(b, a)
	gcd2 = gcd(d, c)
	gcd3 = gcd(max(gcd1, gcd2), min(gcd1, gcd2))
	lcm = int(gcd1 * gcd2 / gcd3)
	c = k // lcm
	if c == 0:
		print(1)
	else:
		print(c * 2 + 1)


def gcd(A, B):
	while A != B:
		if A > B:
			A -= B
		else:
			B -= A
	return A
for T in range(int(input())):
	(A, B, C, D, K) = [int(x) for x in input().split()]
	GCD_1 = gcd(A, B)
	GCD_2 = gcd(C, D)
	GCD = gcd(GCD_1, GCD_2)
	LCM = int(GCD_1 * GCD_2 / GCD)
	count = int(K // LCM)
	count *= 2
	count += 1
	print(count)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	a = input()
	a = a.split()
	ab = gcd(int(a[0]), int(a[1]))
	cd = gcd(int(a[2]), int(a[3]))
	com = gcd(ab, cd)
	lcm = ab * cd // com
	ans = int(a[4]) // lcm
	ans = ans * 2 + 1
	print(ans)


def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
for T in range(int(input())):
	(A, B, C, D, K) = [int(x) for x in input().split()]
	GCD_1 = gcd(B, A)
	GCD_2 = gcd(D, C)
	GCD = gcd(max(GCD_1, GCD_2), min(GCD_1, GCD_2))
	LCM = GCD_1 * GCD_2 // GCD
	count = int(K // LCM)
	count *= 2
	count += 1
	print(count)


def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	while a % b != 0:
		a = a % b
		(a, b) = (b, a)
	return b
for i in range(int(input())):
	(a, b, c, d, k) = [int(i) for i in input().split()]
	p1 = gcd(a, b)
	p2 = gcd(c, d)
	p3 = p1 * p2 // gcd(p1, p2)
	print(2 * (k // p3) + 1)


def GCD(u, v):
	while v:
		(u, v) = (v, u % v)
	return abs(u)
Output = []
n = eval(input())
for i in range(n):
	a = input().split()
	gcd1 = GCD(int(a[0]), int(a[1]))
	gcd2 = GCD(int(a[2]), int(a[3]))
	divisor = gcd1 * gcd2 // GCD(gcd1, gcd2)
	Output.append(int(a[4]) // divisor * 2 + 1)
for i in Output:
	print(i)


def gcd(x, y):
	if x == 0:
		return y
	return gcd(y % x, x)
t = int(input())
for i in range(t):
	(a, b, c, d, k) = map(int, input().split())
	g1 = gcd(a, b)
	g2 = gcd(c, d)
	lc = g1 * g2 // gcd(g1, g2)
	print(k // lc * 2 + 1)


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

def lcm(a, b):
	return a * b / gcd(a, b)
t = int(input())
for i in range(t):
	inp = input().split(' ')
	r = []
	for i in inp:
		r.append(int(i))
	f = gcd(r[0], r[1])
	s = gcd(r[2], r[3])
	step = int(lcm(f, s))
	print(r[4] // step * 2 + 1)


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

def main():
	T = int(input())
	for x in range(T):
		L = input().split()
		L = [int(a) for a in L]
		gcd1 = gcd(L[0], L[1])
		gcd2 = gcd(L[2], L[3])
		gcd3 = gcd(gcd1, gcd2)
		lcm = int(gcd1 * gcd2 / gcd3)
		result = 2 * (L[4] // lcm) + 1
		print(result)
main()


import math
import sys
tc = int(input())
for tcase in range(tc):
	(a, b, c, d, k) = map(int, input().split())
	g = math.gcd(a, b)
	f = math.gcd(c, d)
	lcm = g * f // math.gcd(g, f)
	d = k // lcm
	ans = 2 * d + 1
	print(ans)


from math import gcd

def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(a, b, c, d, k) = li()
	g1 = gcd(a, b)
	g2 = gcd(c, d)
	g3 = gcd(g1, g2)
	print(2 * (k // (g1 * g2 // g3)) + 1)


def gcd(a, b):
	if a % b == 0:
		return b
	elif b % a == 0:
		return a
	elif a > b:
		return gcd(b, a % b)
	elif b > a:
		return gcd(a, b % a)
t = int(input())
for i in range(t):
	inp = list(map(int, input().split()))
	a = inp[0]
	b = inp[1]
	c = inp[2]
	d = inp[3]
	k = inp[4]
	p = gcd(a, b)
	q = gcd(c, d)
	s = gcd(p, q)
	r = p * q // s
	ans = k // r
	print(2 * ans + 1)


import math
t = int(input())
for i in range(t):
	(a, b, c, d, k) = map(int, input().split())
	g1 = math.gcd(a, b)
	g2 = math.gcd(c, d)
	g = math.gcd(g1, g2)
	m = g1 * g2 // g
	ans = k // m
	print(ans * 2 + 1)


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

def run():
	(a, b, c, d, k) = map(int, input().split())
	(dx, dy) = (gcd(a, b), gcd(c, d))
	l = dx * dy // gcd(dx, dy)
	print(k // l * 2 + 1)
t = int(input())
for i in range(t):
	run()