Migrated from Lutece 343 Sixth Grade Math

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In sixth grade, students are presented with different ways to calculate the Least Common Multiple (LCM) and the Greatest Common Factor (GCF) of two integers. The LCM of two integers $a$ and $b$ is the smallest positive integer that is a multiple of both $a$ and $b$ . The GCF of two non-zero integers $a$ and $b$ is the largest positive integer that divides both $a$ and $b$ without remainder.

For this problem you will write a program that determines both the LCM and GCF for positive integers.

Input

The first line of input contains a single integer $N$ , ($1\leq N\leq 1000$) which is the number of data sets that follow. Each data set consists of a single line of input containing two positive integers, $a$ and $b$ , ($1\leq a, b\leq 1000$) separated by a space.

Output

For each data set, you should generate one line of output with the following values: The data set number as a decimal integer (start counting at one), a space, the LCM, a space, and the GCF.

Samples

3 
5 10 
7 23 
42 56

1 10 5 
2 161 1 
3 168 14

Resources

Greater New York 2008