Faktorizacija
We say that two prime numbers p1 and p2 are k-prime apart if there are exactly k prime numbers between them. You are given integers N and k, such that N is either prime or can be written in the form p1 · p2 · p3 · · · · · pm, where for each i ∈ {1,2,...,m−1} it holds that 1 < pi < pi+1, and pi and pi+1 are k-prime apart. Your task is to factorize N, i.e. write it in the form of a product of prime numbers.
InputFrom the first line of the standard input read the integer T (1 ≤ T ≤ 5000), representing the amount of test cases. From the following T lines, read two integers N and K (2 ≤ N ≤ 10^12, 0 ≤ K ≤ 100).
OutputWrite T lines to the standard output, where the ith line contains the factorisation of the integer N given in the ith testcase. Write the factors of N in ascending order and between each two numbers write the character '*' (star).
Input:
Output:
4
238 2
11 0
2431 0
10 1Output:
2*7*17
11
11*13*17
2*5Remark. In 20% of all test cases, N ≤ 10^6.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.