I. The Secret Key
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kalu is a computer engineer working for an agency that needs to send and receive encrypted messages. The agency has given him a transmitter that contains a special number $$$A$$$ and a receiver that contains a special number $$$B$$$. These two devices need to communicate with each other securely using a shared secret, which is an integer $$$X$$$.

The shared secret $$$X$$$ must satisfy two properties:

  • When you divide the transmitter's number $$$A$$$ by $$$X$$$, the remainder is $$$m_1$$$.
  • When you divide the receiver's number $$$B$$$ by $$$X$$$, the remainder is $$$m_2$$$.
Your job is to write a program that finds the smallest positive integer $$$X$$$ that satisfies these properties.

Note: When dividing the integer $$$a$$$ by the integer $$$b$$$, the remainder is a unique integer $$$c$$$ satisfying $$$0\leq c \lt b$$$ and the property that $$$a-c$$$ is divisible by $$$b$$$.

Input

The first line of input consists of an Integer $$$T$$$ $$$(1 \le T \le\ 5\cdot10^5)$$$ denoting the number of test cases. Each of the following $$$T$$$ lines contains four integers separated by a space: $$$A$$$, $$$B$$$, $$$m_1$$$, and $$$m_2$$$ $$$(1 \le A, B \le 5\cdot10^5 , \,0 \le m_1, m_2 \le 5\cdot10^5 )$$$.

Output

For each test case, print the secret key $$$X$$$ if it exists. Otherwise, print $$$-1$$$.

Example
Input
3
2 4 0 0
3 6 1 0
10 10 2 6
Output
1
2
-1