Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Love for Mother

By Sanjida1903070 · Limits 1s, 512 MB

Muntasir is a university student. His mother is struggling with 3 blocks in her heart and her condition is very serious. He lost his father long ago. For the treatment of his mother, he needs a big amount of money. That’s why he does a lot of tuitions and besides tuitions, he also teaches at a coaching center. However, Muntasir loves teaching. He always tries to encourage his students to study.

He teaches math at coaching. Sometimes he gives some interesting maths to his students. Now, we will talk about one of these maths. The math statement is like that “You have 3 types of chocolates and a,b,ca, b, c numbers of each type. You want to distribute the chocolates among the maximum number of children in such a way that after distributing each type of chocolates equally there will be x,y,zx, y, z numbers of chocolates left of each type.”

For more clarification “If you distribute the chocolates among nn children and give p,q,rp, q, r numbers of each type to each child then n×p+x=an\times p+x=a, n×q+y=bn\times q+y=b and n×r+z=cn\times r+z=c. Now, you have to maximize nn.”

Note: After distributing, each child must get at least one chocolate of each type.

As a programmer, can you find the answer to the math before Muntasir’s students?

Input

Input starts with an integer T(1T100)T (1 ≤ T ≤ 100), denoting the number of test cases.

The first line of each test case contains three integers a,b,c(1a,b,c1018)a, b, c (1 ≤ a, b, c ≤ 10^{18}).

The second line of each test case also contains three integers x(0xa),y(0yb),z(0zc)x(0 ≤ x ≤ a), y(0 ≤ y ≤ b), z(0 ≤ z ≤ c).

Output

For each test case, If it's impossible to fulfill the requirements, print "Impossible"(without quotes). Otherwise, print one integer, the maximum number of children who will get chocolates.

Sample

InputOutput
2
29 50 75  
1 2 3
1 1 1
1 1 1
4
Impossible

    Discussion

    Statistics


    70% Solution Ratio

    UshanGhoshEarliest, 1w ago

    Amim_15Fastest, 0.0s

    MahiyatLightest, 0 B

    IFdi11.Shortest, 309B

    Submit

    Login to submit

    Related Contests