Description

Given three positive integers x, y, and z, compute their greatest common divisor (GCD) and least common multiple (LCM). The GCD of two or more numbers is the largest positive integer that can divide each of those numbers. The LCM of two or more numbers is the smallest positive integer that can be divided by each of those numbers.

Input

The first line contains a positive integer T (T<=1000), which indicates the number of test cases in the input. In the next T lines, each line contains three positive integers x, y, and z, each of which is not greater than 10^6.

Output

For each case, print the GCD and LCM of x, y, and z in a line. Note that you have to add '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

For a sequence {X1, X2, …, Xn}, we call (i,j) an "inversion pair" if Xi > Xj and i < j. Given a sequence, calculate the number of inversion pairs in this sequence.

Input

There are multiple test cases. Each case begins with an integer n, followed by n integers from X1 to Xn. The input is terminated when n=0.

Output

For each test case, print the number of inversion pairs in the given sequence. Note that you have to add '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a list of English words, rearrange the words in lexicographic (dictionary) order, which is similar to how the English words are listed in an English dictionary. That is, given two words W1 and W2, we compare them character by character. If the ASCII code of the first character of W1 is smaller than the first character of W2, we said that W1 is smaller than W2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If W1 is W2’s prefix, then W1 is smaller than W2, for example, “cool” is a prefix of “coolness” so “cool” is considered to be smaller than “coolness”.

Input

There are multiple test cases. Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line.  The maximum length of words is 50. The alphabets are 26 lowercase letters ‘a’ to ‘z’. The input ends when N = 0.

Output

For each test case, print the words in lexicographic order. Print a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Write a program to simulate a queue of English names. There are three operations:

1. "Push [name]", which means to enque the name into the queue.

2. "Pop", which means to deque. If the queue is empty, this operation takes no effect.

3. "Front", which means to print the name that is at the front of the queue. If the queue is empty, print "empty" (without quotes).

Input

Each line contains one of the following operations: Push [name], Pop, Front. The length of each name is at most 10.

Output

For each "Front" operation, print out the name that is at the front of the queue. Note that you have to add '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please compute the sum of two given n-bit binary numbers.

Input

The first line of the input file contains a positive integer T indicating the number of test cases. The first line of each test case is a positive integer n denoting the length of bits. The second and third lines are the two n-bit binary numbers. The first bit of each binary number is always 0, which guarantees that the sum of the two binary numbers can still be expressed as an n-bit binary number.

Case1 : t<=100, n<=100
Case2 : t<=200, n<=1000
Case3 : t<=300, n<=5000
Case4 : t<=400, n<=10000

Output

For each test case, your program should print the sum in the same format as the binary numbers given in input.

Sample Input  Download

Sample Output  Download

Tags

Discuss