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