Two Jugs

Time limit2sMemory limit256 MB

Summary

Given two jug capacities and a target volume, decide whether fill, empty, and pour operations can leave exactly that volume in one jug.

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

Problem

You have two empty jugs and a tap that fills a jug. The tap can only fill a jug all the way, because the jugs carry no volume markings and you cannot stop at a chosen level.

You may empty either jug at any time.

You may also pour water from one jug into the other. If the poured water is more than the receiving jug can still take, the receiving jug ends up full and the rest stays in the jug it came from.

Given the volumes of the two jugs, decide whether one of them can end up holding exactly the wanted volume of water.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 10^5$ ). Each of the next $T$ lines contains three integers $a$ , $b$ , and $d$ separated by spaces. Here $a$ and $b$ are the volumes of the two jugs ( $1 \le a, b \le 10^7$ ), and $d$ is the volume of water you want ( $0 \le d \le \max(a, b)$ ).

Output

For each test case, print one line. Print Yes if one of the two jugs can hold exactly $d$ units of water, and No otherwise.

Examples2

Example 1
Input
```
3
8 1 5
4 4 3
5 3 4
```
Expected output
```
Yes
No
Yes
```

Example 2

Input

Expected output

Yes
Yes
Yes
No