Дано цілі невід'ємні числа n та k. Потрібно знайти розклад значення C(n,k) на прості множники.

   Вхідні дані

   Перший рядок містить кількість тестів t (t ≤ 10). Кожний з наступних t рядків опиує один тест і містить числа n та k (0 ≤ n ≤ 100000, 0 ≤ k ≤ n), відокремлені пропуском.

   Вихідні дані

   Надрукувати t рядків, кожний з якихмістить розклад числа C(n,k) на прості множники для відповідного тесту.

   Розклад натурального числа N на прості множники слід виводити наступним чином. Якщо N = 1, то необхідно вивести "1" (без лапок), інакше нехай N = p₁^a₁ * ... * p_d^a_d, де p₁, ..., p_d - всі різні прості дільники числа N, впорядковані за зростанням, і a₁, ..., a_d - натуральні числа (a_i дорівнює максимальній степені, у якій p_i ділить N). Тоді необхідно вивести рядок виду

p₁[^a₁] * p₂[^a₂] * ... * p_d[^a_d]

   Тут [^a_i] означає, що необхідно не писати ^a_i, якщо a_i = 1.