# Биномиальный коэффициент

# 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**), separated by space.

**≤**k**≤**n**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**are all different prime factors of the number

_{1}, ..., p_{d}**N**sorted in increasing order and

**a**are positive integers (

_{1}, ..., a_{d}**a**is equal to the maximal degree of power of

_{i}**p**which divides

_{i}**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**if

_{i}**a**.

_{i}= 13 1 1 4 2 6 3

1 2 * 3 2^2 * 5