Bholu the Pandit on this New Year wanted to divide his Cuboidal Packaging block into cubes. But he loves uniformity so he asks you to divide it such a way that all the cubes are of same size and volume of individual cube is as large as possible.

Note: He will utilize whole volume i.e volume of cuboid before dividing is same as sum of volume of all the cubes.

Input
The first input line contains an integer T, the number of testcases. Each testcase consist of single line which consist of 3 space separated integers a, b & c representing length, breadth and height of the Cuboidal block.

Output
For each testcase you need to output 2 space separated integers, the length of side of the cube and the number of cubes which could be formed out of this cuboidal packaging block. As the number of cubes which could be made could be a large number so just output the answer modulus 10⁹+7 (1000000007).

Constraints
1 ≤ T ≤ 1000
1 ≤ a,b,c ≤ 10⁹

SAMPLE INPUT    

2
2 4 6
1 2 3

SAMPLE OUTPUT    

2 6
1 6

  Explanation

In the 1st testcase a=2, b=4 & c=6. So length of the side of the cube would be 2 and the number of cubes which would be formed would be 6. In the 2nd testcase a=1, b=2 & c=3. So length of the side of the cube would be 1 and the number of cubes which would be formed would be 6.

Time Limit:1.0 sec(s) for each input file. Memory Limit:256 MB Source Limit:1024 KB Marking Scheme:Marks are awarded when all the testcases pass. Allowed Languages:Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

 

Approach # 1: 

/*
// Sample code to perform I/O:

#include <iostream>

using namespace std;

int main() {
	int num;
	cin >> num;										// Reading input from STDIN
	cout << "Input number is " << num << endl;		// Writing output to STDOUT
}

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
#include<iostream>
#include<algorithm>
const int mod = 1e9 + 7;

using namespace std;

long long gcd(long long x, long long y) {
    if (y == 0)
        return x;
    else return gcd(y, x%y);
}

int main() {
    int n;
    long long l, w, h;
    long long ans;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l >> w >> h;
        long long c = gcd(gcd(l, w), h);
        l /= c;
        w /= c;
        h /= c;
        ans = (((l * w) % mod) * h) % mod;
        cout << c << ' ' << ans << endl;
    }
    
    return 0;
}

　　

Analysis:

From this problem I learned how to deal with the three numbers problem. And we shuold use long long.