Даны целые неотрицательные числа n и k. Найти разложение биномиального коэффициента C(n, k) на простые множители.

Входные данные

Первая строка содержит количество тестов t (t ≤ 10). Каждая из следующих t строк является отдельным тестом и содержит числа n и k (0 ≤ n ≤ 105, 0 ≤ k ≤ n).

Выходные данные

Вывести t строк, каждая из которых содержит разложение числа C(n,k) на простые множители для соответствующих входных значений.

Разложение натурального числа N на простые множители следует выводить следующим образом. Если N = 1, то необходимо вывести "1" (без кавычек). Иначе пусть N = p1^a1 ... pd^ad, где p1, ..., pd - все различные простые делители числа N, упорядоченные по возрастанию, и a1, ..., ad - натуральные числа (ai равно максимальной степени, в которой pi делит N). Тогда необходимо вывести строку вида p1[^a1] * ... * pd[^ad]. Здесь [^ai] означает, что не следует писать ^ai, если ai = 1.