Даны целые неотрицательные числа 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.