6064 - 수학(GCD, LCM)

챌린징 포인트
1. lcm 단순히 약수에서 중복제거하는 방식으로 구현. N^2 나올 수 밖에 없음
x*y // gcd(x,y)로 처리 가능
*gcd연산은 PS_LIB에 저장해둔것 활용 혹은 gcd 임포트해서 써도 된다.
2. 하나씩 연산하면 16억 가량에대해 계속 ++해줘야해서 불가.(시간초과)
3. 결국 m,n중 큰걸 생각하고 그것의 나머지에 대해서 작은 값에서도 동일한 수가 나와야함을 알고
4. 값을 추가해서 연산

??? % n = y
??? % m = x
동일한 수 ???을 찾으면 해결. (예외처리는 나누어 떨어지는 경우)

import sys
from math import gcd

n = int(input())
case = []
for _ in range(n):
	case.append(list(map(int,sys.stdin.readline().strip().split())))


def f_lcm(x,y):
	return (x * y // gcd(x,y))

def matth(arr):
	m = arr[0]
	n = arr[1]
	x = arr[2]
	y = arr[3]
	lcm = f_lcm(m,n)
	if m == n:
		if x != y:
			return -1
		else:
			return x
	if m == x and n == y:
		return lcm
	if m > n: #초기값x + m*정수 만큼 곱=>기준으로해서 확인할것.  stand%n == y일경우 리턴
		stand = m
		nostand = y
		init = x
		mmod = n
	else:
		stand = n
		nostand = x
		init = y
		mmod = m
	i = 0
	while((init + (stand*i)) <= lcm):
		temp = ((init + (stand*i)) % mmod)
		if temp == 0:
			if nostand == mmod:
				return (init + (stand*i))
		if (temp == nostand):
			return (init + (stand*i))
		i+=1
	return -1


for c in case:
	print(matth(c))