## MAY99_3 - Easy Jug

no tags

One day Manku was very thirsty so he decided to drink exactly z litres of water. However , in front of him, there is a well of infinite amount of water and 2 empty jugs of quantity x litres and y litres respectively.

Now Manku can do the following operations to any jug

1. Fill it completely from the well
2. Empty it entirely
3. Transfer as much water from Jug 1 to Jug 2, till Jug 1 gets empty or Jug 2 is completely filled.

Now since he has no measuring device so he will do these operations only to make any of the 2 jug having exactly z litres of water.

Now Your task is given value of x, y, z, tell whether it is possible for Manku to drink water or not.

### Input

First Line of Input contains T, the number of test cases. (T <= 25)

Then for each test case there are 3 numbers x, y, z given in separate line.

• 1 <= x <= 10^8
• 1 <= y <= 10^8
• 1 <= z <= 10^8

### Output

For each test case outputĀ "YES" if manku can drink exactly z litres of water else "NO".

### Example

```Input:
5
2 4 3
2 5 1
9 3 6
3 8 7
6 1 10

Output:
NO
YES
YES
YES
NO```

### Explanation

• In Test case 1 Either Manku can have 2 or 4 litres of water so he cant drink 3 litres.
• In Test case 2 Manku can have 1 litre water by doing the following operations:
• -> Fill 2 litre Jug
• -> Transfer its water to 5 litre Jug
• -> Again Fill 2 litre Jug
• -> Again Transfer its entire water to 5 litre Jug
• Now 5 litre Jug will have total 4 litre water
• -> Again Fill 2 litre Jug
• -> Now transfer 1 litre water to 5 litre Jug
• because at present 5 litre Jug don't have space for more than 1 litre water
• Now the 2 litre Jug will have only 1 litre water left
• For Test case 3 we will transfer 3 litre water twice from 3 litre jug to 9 litre jug
• For test Case 4,
• transfer 3 times water of 3 litre jug to 8 litre jug
• Ultimately 3 litre Jug has 1 litre water left and 8 litre Jug is full
• Now empty 8 litre jug and pour remaining 1 litre of 3 litre jug in it
• Now fill 3 litre jug fully twice and transfer its water to 8 litre jug
• Now 8 litre Jug will have 7 litre water
• For Test case 5, we cant have 10 litre of water in any jug