Water Jug Problem Statement

You have two water jugs with capacities X and Y liters respectively, both initially empty. You also have an infinite water supply. The goal is to determine if it is possible to measure exactly Z liters using these two jugs and the operations outlined below.

Operations Allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another until the other jug is full or the first jug is empty.

Input:

The input consists of multiple test cases. The first line contains an integer 'T' representing the number of test cases. The next T lines each contain three space-separated integers X, Y, and Z indicating the capacities of both jugs and the target measurement, respectively.

Output:

For each test case, output 'True' if it's possible to measure exactly Z liters, otherwise output 'False'. Each result should be on a new line.

Example:

To measure 2 liters using jugs with capacities 4 and 6 liters:

• Fill the 6-liter jug completely.
• Transfer from the 6-liter jug to the 4-liter jug until the latter is full.
• Repeat the transfer from the 6-liter jug to the 4-liter jug.

Constraints:

• 1 ≤ T ≤ 5 * 104
• 0 ≤ X, Y, Z ≤ 5 * 104
• Time Limit: 1 second

Note:

You do not need to print anything; the printing is handled externally. Simply implement the required function.