처음에 문제를 봤을 때, 알고리즘 태그에 중국인의 나머지 정리가 있는 것을 보고 잘 모르는 알고리즘이라서 바로 해설부터 찾아봤었는데, 사실 몰라도 풀 수 있는 문제였습니다.
import sys
input = sys.stdin.readline
print = sys.stdout.write
# 최대공약수
def gcd(a, b):
if b == 0 : return a
return gcd(b, a % b)
# 최소공배수
def lcm(a, b) : return a * b // gcd(a, b)
TC = int(input())
for tc in range(TC):
M, N, x, y = map(int, input().split())
b = N if x % N == 0 else x % N
k = x
L = lcm(M, N)
while k <= L and b != y:
b = N if (b + M) % N == 0 else (b + M) % N
k += M
print(str(k if b == y else -1))
print("\n")