Faktorizacija
Za proste brojeve p1 i p2 ćemo reći da su k-prosto udaljeni ukoliko izmedju njih postoji tačno k prostih brojeva. Vama su dati brojevi N i k, pri čemu znamo da je broj N ili prost ili se može zapisati u obliku proizvoda p1 · p2 · p3 · · · · · pm, gde znamo da za svako i ∈ {1,2,...,m−1} važi 1 < pi < pi+1 i pi i pi+1 su k-prosto udaljeni brojevi. Vaš zadatak je da faktorišete broj N, tj. da ga napišete u obliku proizvoda prostih brojeva.
InputU prvom redu standardnog ulaza se nalazi broj T (1 ≤ T ≤ 5000), koji predstavlja broj upita. U sledećih T redova se nalaze brojevi N i K (2 ≤ N ≤ 10^12, 0 ≤ K ≤ 100).
OutputNa standardni izlaz je potrebno ispisati T redova, gde je u i-tom redu ispisana faktorizacija broja N koji je dat u i-tom upitu. Činioce broja N ispisati u rastućem poretku i izmedju svaka 2 broja ispisati znak ’*’ (zvezdica).
Ulaz:
Izlaz:
4
238 2
11 0
2431 0
10 1Izlaz:
2*7*17
11
11*13*17
2*5Napomena. U 20% test primera je 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.