Baeknam's Preparation for Travel Preparation

Time limit3sMemory limit512 MB

Summary

Given moduli A, B, C and remainders a, b, c, find the smallest nonnegative integer satisfying all three congruences, or -1 if none exists.

Level: Medium6 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Cute Baeknam is on vacation and getting ready to set off on a trip.

Before preparing for the trip, Baeknam plans to smash open his piggy bank to fund the purchase of necessities. He ends up with a lot of gold coins, and he becomes curious about how many there are.

With a T (thinking) MBTI type, Baeknam wants to work out the number of gold coins in an unusual way, to sharpen his thinking.

Baeknam's method for finding the number of gold coins is as follows.

He prepares three special boxes. Each box has a number engraved on it, and those numbers are $A$ , $B$ , $C$ . When an object is placed in a box, the box reveals the remainder when the number of objects is divided by the engraved number. Let the numbers produced by putting the gold coins into the boxes be $a$ , $b$ , $c$ . Find how many gold coins Baeknam has.

Input

The first line gives the number of test cases $T$ . ( $1 \le T \le 1,000,000$ )

Each test case takes one line. Each line gives six integers $A$ , $B$ , $C$ , $a$ , $b$ , $c$ .

( $1 \le A,\;B,\;C\le1,000,000$ ) ( $0 \le a < A$ ) ( $0 \le b < B$ ) ( $0 \le c < C$ )

Output

For each test case, print the number of gold coins. If several numbers of gold coins are possible, print the smallest one.

If no solution exists for the given integers, print -1.

Examples1

Example 1

Input

4
4 3 2 0 2 0
8 4 2 4 2 1
19 52 25 7 50 2
14 23 51 13 22 50

Expected output