Біноміальні коефіцієнти 2

Вхідні дані

Перший рядок містить кількість тестів $t (t \leq 10)$ t~(t \le 10). Кожен з наступних $t$ рядків є окремим тестом і містить два цілих числа $n$ і $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).

Вихідні дані

Виведіть $t$ рядків, кожен з яких має містити розклад числа $C_{n}^{k}$ C_n^k на прості множники.

Розклад натурального числа $n$ на прості множники слід виводити наступним чином.

Якщо $n = 1$ n = 1, виведіть $1$ .

Інакше нехай

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

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

де $p_{1}, \dots, p_{d}$ p_1, \ldots, p_d — різні прості дільники числа $n$ , розташовані в порядку зростання, а $a_{1}, \dots, a_{d}$ a_1, \ldots, a_d — їх відповідні додатні степені.

Тоді виведіть рядок виду

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

Степінь $a_{i}$ a_i виводити не слід, якщо $a_{i} = 1$ a_i = 1.

Приклади

Приклад 1

Loading