Binomial coefficients 2

Input

The first line contains the number of tests $t (t \leq 10)$ t~(t \le 10). Each of the following $t$ lines represents a separate test case and contains two integers $n$ and $k (0 \leq n \leq 1 0^{5}, 0 \leq k \leq n)$ k~(0 \le n \le 10^5, 0 \le k \le n).

Output

Print $t$ lines, each of which should contain the prime factorization of $C_{n}^{k}$ C_n^k.

The prime factorization of a positive integer $n$ must be printed as follows.

If $n = 1$ n = 1, print $1$ .

Otherwise, let

n = p_{1}^{a_{1}} \times \dots \times p_{d}^{a_{d}},

n = p_1^{a_1} \times \ldots \times p_d^{a_d},

where $p_{1}, \dots, p_{d}$ p_1, \ldots, p_d are the distinct prime divisors of $n$ in increasing order, and $a_{1}, \dots, a_{d}$ a_1, \ldots, a_d are their corresponding positive exponents.

Then print the expression in the format

p_{1} ˆ a_{1} * p_{2} ˆ a_{2} * \dots * p_{d} ˆ a_{d}

p_1~\text{\^{}}~ a_1 * p_2~\text{\^{}}~ a_2 * \ldots * p_d~\text{\^{}}~ a_d

The exponent $a_{i}$ a_i should be omitted if $a_{i} = 1$ a_i = 1.

Examples

Example 1

Loading