Tienes dos jarras de capacidades \(x\) e \(y\) litros, sin marcas, y agua ilimitada. Puedes llenar una jarra, vaciarla o trasvasijar de una a otra hasta que la primera se vacíe o la segunda se llene. Decide si es posible terminar con exactamente \(t\) litros en total entre las dos jarras.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 10^5)\). Cada una de las siguientes \(T\) líneas tiene \(x\), \(y\) y \(t\) \((1 \le x, y \le 10^9, 0 \le t \le 2 \cdot 10^9 + 1)\).

Salida

Para cada caso, una línea con true o false.

Ejemplo 1

Entrada

3
3 5 4
2 6 5
1 2 3

Salida

true
false
true