InternDoor

Reach the pair by adding

Hardmath · number theoryRead the input, print the output

Reported in interviews at (where)

You start with a pair of whole numbers (x, y). In one move you may add either number to the other: (x, y) becomes (x + y, y) or (x, x + y).

For each test, say whether (a, b) can be turned into (c, d) with some number of moves, none included.

The numbers go up to 10^15, so trying moves forwards is hopeless. Work backwards: every pair you can reach has exactly one pair it came from.

Input

The first line holds T, the number of tests. Each test is one line holding four whole numbers: a, b, c and d.

Output

For each test, one line: Yes if (c, d) can be reached from (a, b), otherwise No.

Example
Input
4
1 1 3 5
1 1 2 2
2 3 2 3
4 7 4 22
Output
Yes
No
Yes
No
  1. (1, 1) becomes (1, 2), then (3, 2), then (3, 5).
  2. After any move the two numbers differ, so (2, 2) is never reached.
  3. No moves are needed.
  4. With the first number staying 4, the second goes 7, 11, 15, 19, 23 and misses 22.

Limits

  • 1 <= T <= 1000
  • 1 <= a, b, c, d <= 1000000000000000

Hints

Hint 1

After a move the two numbers differ, and the bigger one is the one that just grew. So going backwards there is only one way: subtract the smaller number from the bigger.

Hint 2

Subtracting the same number many times in a row is a remainder: replace the bigger number by its remainder after dividing by the smaller, but stop exactly at a or b when that coordinate can no longer change.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.