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.
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$ .
For each test, print YES if it is possible to measure the water and NO otherwise.
7 5 3 4 1 1 1 1 1 2 2 2 1 123 456 42 1000 999 123 1000 998 123\n · · \n · · \n · · \n · · \n · · \n · · \n · · \n
YES YES NO NO YES YES NO\n \n \n \n \n \n \n