GCM

সময় লিমিট: 1.0 s

মেমরি লিমিট: 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

Input Output
2
10 15 20 100
1 2 3 6
60
-1

Information

ID
1025
Difficulty
8
Category
(None)
Tags
(None)
# Submissions
38
Accepted
5
Accepted Ratio
13%
Uploaded By

Related

In following contests:

Brain booster #2