Water Containers Queries

There are two water containers: container A has volume a and container B has volume b. You want to measure x units of water using the containers. Initially both containers are empty. On each move, you can fill a container, empty a container or move water from a container to another container. When you move water, you must always fill or empty at least one container. After the moves, container A must have x units of water. Your task is to efficiently check if it is possible to measure the water in several cases.

Input

The first line has integer n: the number of tests. After this, there are n lines. Each line has three integers a, b and x.

Output

For each test, print YES if it is possible to measure the water and NO otherwise.

Constraints

$1 \le n \le 1000$

$1 \le a, b, x \le 10^9$

Example

Input

7
5 3 4
1 1 1
1 1 2
2 2 1
123 456 42
1000 999 123
1000 998 123

Output

YES
YES
NO
NO
YES
YES
NO