MAY99_3  Easy Jug
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
 Fill it completely from the well
 Empty it entirely
 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
hide comments
sonuverma:
20180201 18:56:49
GCD :) 

mahilewets:
20170828 16:59:22
Really easy algorithm


hunnychauhan:
20170720 08:22:16
simple hcf/gcd....


viratian_070:
20170630 20:39:11
euclids extended algorithm works fine 

gajalchouhan:
20170629 13:55:16
using gcd , it will be easy for solving this question. 

karmeshap:
20170317 19:07:29
3289 82394 1 why answer is no for this


mishra_sharad:
20160818 21:35:42
legendary advise..UNDERSTAND EVERY LINE OF PROBLEM CAREFULLY....AND THEN AFTER TAKE THESE TYPES OF COMMENTS VERY SERIOUSLY.... 

akshayvenkat:
20160612 10:05:17
little corner case modification to CEQU and AC! 

lakshay_v06:
20160125 08:50:28
Prerequisites : Diophantine equation and Extended euclids algo. :) 

thedictator:
20151210 13:49:35
too easy if the logic strikes in your mind 
Added by:  Mayank Tuteja 
Date:  20130117 
Time limit:  0.187s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C CPP C++ 4.3.2 CPP14CLANG CPP14 COBOL COFFEE DDMD DCLANG DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM OBJC OBJCCLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 