Competitions

# Binomial coefficients 2

You are given two non-negative integers n and k. Find the factorization of the binomial coefficient C(n, k).

Input

The first line contains the number of test cases t (t 10). Each of the following t lines describes one test case and contains the numbers n and k (0 n 100000, 0 k n), separated by space.

Output

Print t lines, each one should contain the factorization of the number C(n,k) for the corresponding test case.

Prime factorization of the positive integer N should be written in the following way. If N = 1 you should output "1" (without quotes). Else let N = p1a1 * ... * pdad where p1, ..., pd are all different prime factors of the number N sorted in increasing order and a1, ..., ad are positive integers (ai is equal to the maximal degree of power of pi which divides N). Then you should output the line in the form

p1[^a1] * p2[^a2] * ... * pd[^ad]

Here [^ai] means that you should not output ^ai if ai = 1.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1 1
4 2
6 3
Output example #1
1
2 * 3
2^2 * 5

Author Anton Lunyov