Дано два цілих невід'ємних числа \textbf{n} та \textbf{k}. Знайти розклад біноміального коеффіцієнта \textbf{C}(\textbf{n}, \textbf{k}) на прості множники. \InputFile Перший рядок містить кількість тестів \textbf{t} (\textbf{t ≤ 10}). Кожний з наступних \textbf{t} рядків опиує один тест і містить числа \textbf{n} та \textbf{k} (\textbf{0 ≤ n ≤ 100000}, \textbf{0 ≤ k ≤ n}), відокремлені пропуском. \OutputFile Надрукувати \textbf{t} рядків, кожний з якихмістить розклад числа \textbf{C(n,k)} на прості множники для відповідного тесту. Розклад натурального числа \textbf{N} на прості множники слід виводити наступним чином. Якщо \textbf{N = 1}, то необхідно вивести \textbf{"1"} (без лапок), інакше нехай \textbf{N = p_1^a1 * ... * p_d^ad}, де \textbf{p_1, ..., p_d} - всі різні прості дільники числа \textbf{N}, впорядковані за зростанням, і \textbf{a_1, ..., a_d} - натуральні числа (\textbf{a_i} дорівнює максимальній степені, у якій \textbf{p_i} ділить \textbf{N}). Тоді необхідно вивести рядок виду \textbf{p_1\[^a_1\] * p_2\[^a_2\] * ... * p_d\[^a_d\]} Тут \textbf{\[^a_i\]} означає, що необхідно не писати \textbf{^a_i}, якщо \textbf{a_i = 1}.