Prime Factors Identification

Given an integer \( n \) satisfying \(2 \le n \le 100000\), determine its prime factors. If \( n \) is a prime number, output the string Prime. Otherwise, output the prime factors in ascending order (each on a separate line). After printing the result for each dataset, add a blank line.

A prime factor is a divisor of \( n \) that is a prime number. Note that the input will consist of multiple datasets, and the end of input is indicated by a line containing 0 (zero), which should not be processed.

The mathematical condition can be expressed as:

\( n = p_{1}^{a_1} \times p_{2}^{a_2} \times \cdots \times p_{k}^{a_k} \)

where each \( p_i \) is a prime factor and ai is its multiplicity. If \( n \) itself is prime, simply output Prime.

inputFormat

The input consists of multiple datasets. Each dataset is a single positive integer \( n \) (with \(2 \le n \le 100000\)) on a separate line. The input terminates when a 0 (zero) is encountered, which should not be processed.

outputFormat

For each dataset, if \( n \) is prime, print Prime on a single line. Otherwise, print all the prime factors of \( n \) in ascending order, each on a new line. Insert a blank line after the output for each dataset.

## sample

28
17
100
0

2
2
7
Prime
2
2
5
5

</p>