Addy, the pro-coder of BPHC, found data about the number of visitors of ATMOS, the technical fest and PEARL the cultural fest, of his college for each year. He noticed a special property about them that one is an Arithmetic Progression with first term a and Common difference b while the other is a Geometric Progression with first term c and Common ratio d.
AP-https://en.wikipedia.org/wiki/Arithmetic_progression
GP-https://en.wikipedia.org/wiki/Geometric_progression

He started finding the Common terms among the two series but as the data is very large, he asked your help to
find the LEAST Common term among the above two series as soon as possible so that he can spend time enjoying the ATMOS.


Input Format:
First line has one integer T denotes number of Test cases
Next T lines follows each with four integers a, b, c, d as defined above.

Output Format:
For each test case output -1 if Common term doesn’t exist below 10¹⁸ else the LEAST Common term in a newline.

Constraints :
1<=T<=1000
0<=a, b, c<=10¹⁸
0<d<=10¹⁸