You are given two non-negative integers \textbf{n }and \textbf{k}. Find the factorization of the binomial coefficient \textbf{C}(\textbf{n}, \textbf{k}). \InputFile The first line contains the number of test cases \textbf{t} (\textbf{t ≤ 10}). Each of the following \textbf{t} lines describes one test case and contains the numbers \textbf{n} and \textbf{k} (\textbf{0 ≤ n ≤ 100000}, \textbf{0 ≤ k ≤ n}), separated by space. \textbf{ Output} Print \textbf{t} lines, each one should contain the factorization of the number \textbf{C(n,k)} for the corresponding test case. Prime factorization of the positive integer \textbf{N} should be written in the following way. If \textbf{N = 1} you should output \textbf{"1"} (without quotes). Else let \textbf{N = p_1^a1 * ... * p_d^ad} where \textbf{p_1, ..., p_d} are all different prime factors of the number \textbf{N} sorted in increasing order and \textbf{a_1, ..., a_d} are positive integers (\textbf{a_i} is equal to the maximal degree of power of \textbf{p_i} which divides \textbf{N}). Then you should output the line in the form \textbf{p_1\[^a_1\] * p_2\[^a_2\] * ... * p_d\[^a_d\]} Here \textbf{\[^a_i\]} means that you should not output \textbf{^a_i} if \textbf{a_i = 1}.