Background

Special for beginners, ^_^

Description

给一个数对 $\left(𝑎,𝑏\right)$。

每次操作可以令$\left(𝑎,𝑏\right)$变为$\left(𝑎,|𝑎-𝑏|\right)$或$\left(𝑏,|𝑎-𝑏|\right)$。

问最后能否令 $𝑎=x$ 或 $𝑏=x$ 。

Format

Input

第一行一个整数 $T（\le10^6）$，表示数据组数。

就下来 $T$ 行，每行三个不超过 $10^{19}$ 的正整数 $a,b,x$ ，意义如上 。

Output

共 $T$ 行，表示答案。

Samples

8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340

YES
YES
YES
YES
NO
YES
YES
YES

Limitation

1s, 1024KiB for each test case.