Биномиальный коэффициент
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.
3 1 1 4 2 6 3
1 2 * 3 2^2 * 5