Za brojeve p i q kažemo da su k-prosto udaljeni ukoliko su oni prosti i između njih postoji tačno k prostih brojeva. Vama su dati brojevi N i k. Poznato je da je broj N ili prost ili se može zapisati u obliku proizvoda p1·p2·p3·...·pm, gde za svako 1 ≤ i ≤ m - 1  važi pi < p_{i+1} i pi i p_{i+1} su k-prosto udaljeni brojevi. Nažalost, mi ne znamo broj m niti brojeve pi - vaš zadatak je da faktorisete broj N, tj. da ga napišete u obliku proizvoda prostih brojeva.

U jednom test primeru je potrebno faktorisati više brojeva N.

U prvom redu standardnog ulaza se nalazi prirodan broj T - broj parova (N, k) iz opisa problema. U svakom od narednih T redova se nalaze, redom, brojevi N i k, razdvojeni razmakom.

Na standarni izlaz je potrebno ispisati T redova pri čemu je u i-tom redu potrebno ispisati faktorizaciju i-tog broja N sa ulaza. Činioce broja N ispisati u rastućem poretku i između svaka dva činioca ispisati znak '*' (zvezdica) bez razmaka i navodnika (videti dati primer).

1  ≤  T  ≤  5.000

2  ≤  N  ≤  1.000.000.000.000

0  ≤  k  ≤  100

Npr. u prvom paru (N = 238, k = 2), brojevi 2 i 7 su k-prosto udaljeni jer su oni prosti i između njih se nalaze tačno dva prosta broja: 3 i 5. Slično i za brojeve 7 i 17. Faktorizacija broja N pod navedenim uslovima je, naravno, jedinstvena.