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