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 = p_1^a1 * ... * p_d^ad where p_1, ..., p_d are all different prime factors of the number N sorted in increasing order and a_1, ..., a_d are positive integers (a_i is equal to the maximal degree of power of p_i which divides N). Then you should output the line in the form
p_1[^a_1] * p_2[^a_2] * ... * p_d[^a_d]
Here [^a_i] means that you should not output ^a_i if a_i = 1.