Two water jugs

Interview

Time limit2sMemory limit512 MB

Summary

Given two jug capacities a and b, decide whether some sequence of fills, empties, and pours can leave exactly c liters in one jug.

Level: Medium5 of 10
Topics: Math, Number theory, Simulation
Solved: No attempts yet

Problem

You have two jugs with capacities of $a$ and $b$ liters. Water is unlimited, and you may repeat the following three operations as many times as you like.

Fill one jug to the top.
Empty one jug completely.
Pour water from one jug into the other, stopping when the source jug is empty or the receiving jug is full.

Write a program that decides whether you can reach a state where one of the two jugs holds exactly $c$ liters.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 10000$ )

Each of the next $T$ lines contains one test case, given as three integers $a$ , $b$ , $c$ . ( $1 \le a, b, c \le 10^9$ )

Output

For each test case, print YES on its own line if exactly $c$ liters can be measured, and NO otherwise.

Hint

For $a = 5$ , $b = 3$ , $c = 4$ , the following steps produce 4 liters.

Fill $a$ . ( $a = 5$ , $b = 0$ )
Pour $a$ into $b$ . ( $a = 2$ , $b = 3$ )
Empty $b$ , then pour $a$ into $b$ . ( $a = 0$ , $b = 2$ )
Fill $a$ . ( $a = 5$ , $b = 2$ )
Pour $a$ into $b$ . ( $a = 4$ , $b = 3$ )

Examples5

Example 1
Input
```
2
5 3 4
3 6 4
```
Expected output
```
YES
NO
```
Example 2
Input
```
1
1 1 1
```
Expected output
```
YES
```

Example 3

Input

Expected output

YES
YES
YES
NO
NO

Example 4

Input

Expected output

YES
NO
NO
NO

Example 5

Input

Expected output

YES
YES
YES
YES
NO
YES