Даны целые неотрицательные числа n и k. Найти разложение биномиального коэффициента C(n, k) на простые множители.
Первая строка содержит количество тестов t (t ≤ 10). Каждая из следующих t строк является отдельным тестом и содержит числа n и k (0 ≤ n ≤ 10^5
, 0 ≤ k ≤ n).
Вывести t строк, каждая из которых содержит разложение числа C(n,k) на простые множители для соответствующих входных значений.
Разложение натурального числа N на простые множители следует выводить следующим образом. Если N = 1, то необходимо вывести "1" (без кавычек). Иначе пусть N = p[1]^a[1]
... p[d]^a[d]
, где p[1]
, ..., p[d]
- все различные простые делители числа N, упорядоченные по возрастанию, и a[1]
, ..., a[d]
- натуральные числа (a[i]
равно максимальной степени, в которой p[i]
делит N). Тогда необходимо вывести строку вида p[1][^a[1]]
* ... * p[d][^a[d]]
. Здесь [^a[i]]
означает, что не следует писать ^a[i]
, если a[i]
= 1.