Time Limit: 1.0 s

Memory Limit: 32.0 MB

Description

Lets define GCM(X) as the greatest common multiple of some positive integer, less than X.

You are given three positive integer a,b,c and the parameter X. find the GCM of a,b,c less than X.If there is no common multiple less than X print -1.

Input

First line of input takes an integer T: number of testcases
each testcase takes 4 integers a,b,c,X: three positive integer and the parameter X

\(1 <= T <= 10^3\)
\(1 <= a,b,c <= 10^9\)
\(1 < X <= 10^{12}\)

Output

Output T integers in each line: the GCM of a,b,c less than X or -1.

Sample

2
10 15 20 100
1 2 3 6

60
-1