OPC1708D - Measuring Water

Lets solve a puzzle. :)

You are given two beakers of capacity c1 ltrs and c2 ltrs.You have to find out whether you can measure exactly C ltrs of beer using them?

Input

The first line contains t, the number of test cases. (t <= 1000)

Then t lines follow. Each test case contains three space separated integers c1, c2 and C. (0 < c1, c2, C <= 10^15)

You can use the smaller beakers any number of times and assume you have infinite amount of beer in some measuring tank.

Output

Output "YES" (quotes for clarity only) if it is possible to measure C litres using c1 and c2, else output "NO".

Example

Input:
1
2 3 5

Output:
YES

Added by:bashrc is back
Date:2012-08-17
Time limit:0.5s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.