X-Magic Pair solution codeforces

You are given a pair of integers (𝑎,𝑏)(a,b) and an integer 𝑥x.

You can change the pair in two different ways:

  • set (assign) 𝑎:=|𝑎𝑏|a:=|a−b|;
  • set (assign) 𝑏:=|𝑎𝑏|b:=|a−b|,

where |𝑎𝑏||a−b| is the absolute difference between 𝑎a and 𝑏b.The pair (𝑎,𝑏)(a,b) is called 𝑥x-magic if 𝑥x is obtainable either as 𝑎a or as 𝑏b using only the given operations (i.e. the pair (𝑎,𝑏)(a,b) is 𝑥x-magic if 𝑎=𝑥a=x or 𝑏=𝑥b=x after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair (𝑎,𝑏)(a,b) is 𝑥x-magic or not.

You have to answer 𝑡t independent test cases.

Input X-Magic Pair solution codeforces

The first line of the input contains one integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The next 𝑡t lines describe test cases.

The only line of the test case contains three integers 𝑎a𝑏b and 𝑥x (1𝑎,𝑏,𝑥10181≤a,b,x≤1018).

Output

For the 𝑖i-th test case, print YES if the corresponding pair (𝑎,𝑏)(a,b) is 𝑥x-magic and NO otherwise.

Example X-Magic Pair solution codeforces

input

Copy
8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340
output

Copy
YES
YES
YES
YES
NO
YES
YES
YES

 

Leave a Comment

Your email address will not be published. Required fields are marked *