6064: 카잉 달력

• 브루트포스로 풀면 시간 초과가 발생함
• x % N == y % N을 만족하는 x, y가 있는지 확인해야함
  -> x를 N으로 나눈 나머지가 y를 N으로 나눈 나머지와 같을 때까지 x에 M을 더해줌

import sys

T = int(input())

for _ in range(T):
    tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
    M = tmp[0]; N = tmp[1]; x = tmp[2]; y = tmp[3]
    
    flag = 0
    while(x <= M * N):
        if x % N == y % N:
            print(x)
            flag = 1
            break
        x += M
    if flag == 0:
        print(-1)