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, until 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
vatsal rastogi: 2013-03-20 22:23:29

Can anybody provide some test-cases?

Ouditchya Sinha: 2013-03-02 09:06:17

@conioh you are right... AC :)

suyog patil: 2013-02-15 15:27:09

easy one!!!

Sai Nikhil: 2013-02-10 11:49:59

hey, why last test case is no ?

1*6+4*1 = 10 right ?

nimish: 2013-01-26 13:17:34

can he drink from both the jugs,when situation comes like x=6,y=1,z=7

conioh: 2013-01-25 14:17:17

I think this question is simpler version of POUR1.

Last edit: 2013-01-25 14:17:35
OKUDA Yoshifumi: 2013-01-25 07:40:38

Case 2
Fill 5-liter jug
Pour water from 5-liter jug to fill 2-liter jug
Empty 2-liter jug on ground
Pour water from 5-liter jug to fill 2-liter jug
Now 5-liter jug will have 1 liter water

Last edit: 2013-01-25 11:26:43
abdou_93: 2013-01-24 16:56:10

@Mayank Tuteja
Please check my code ID"8574186 " what is Mistake?
Thanks


Added by:Mayank Tuteja
Date:2013-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET