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₁^a₁ * ... * p_d^a_d where p₁, ..., p_d are all different prime factors of the number N sorted in increasing order and a₁, ..., 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₁[^a₁] * p₂[^a₂] * ... * p_d[^a_d]

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