Quái vật trên sao hỏa


Submit solution

Points: 1 (partial)
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một con quái vật đang đuổi theo Luffy và Zoro trên sao hỏa. Họ cảm thấy rất sợ hãi và thỉnh thoảng còn hét lên.

Luffy hét ở thời điểm b, b + a, b + 2a, b + 3a,...

Zoro hét ở thời điểm d, d + c, d + 2c, d + 3c,...

Con quái vật sẽ bắt được họ ở thời điểm họ hét lên cùng một lúc và nó biết khi nào sẽ bắt được họ.

Input

Dòng đầu chứa số nguyên T là số bộ test (1 <= T <= 50)

T dòng tiếp theo, mỗi dòng chứa 4 số nguyên a, b, c, d (1 <= a, b, c, d <= 100)

Output

Với mỗi bộ test in ra thời điểm Luffy và Zoro bị bắt, nếu họ không bao giờ bị bắt in ra -1

Example

Input

2
20  2   9   19
20  2   9   19

Output

82
82

Comments

There are no comments at the moment.