Recursive GCD

Lab C++ Beginner 10 points

Write long long gcd(long long a, long long b) recursively and print the GCD and LCM of each pair.

Input

n, then n lines a b.

Output

n lines: gcd lcm

Example

Input

Output

6 36
1 85
25 300

Sample input available Sample output available

Editor

C++

Hints

gcd(a, 0) = a.

Solution explanation

Divide before multiplying to keep the LCM from overflowing.

Show solution

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        long long g = gcd(a, b);
        cout << g << " " << a / g * b << "\n";
    }
    return 0;
}

Output

Answer