Prime factors

Problem

Every whole number greater than 1 is a product of prime numbers. For example, 12 = 2 × 2 × 3. A reporting tool lists these prime factors.

Given n, print its prime factors in increasing order, one per line. A factor that appears twice is printed twice.

Example 1

Input

Output

2
2
3

2 × 2 × 3.

Example 2

Input

Output

A prime number is its own only factor.

Try the problem first. Open one hint at a time.

Hint 1

Try the divisor 2 first. While it divides n, print it and divide n by it. Then try 3, 4, 5 and so on.

Hint 2

Stop trying divisors when the divisor squared is bigger than n. If anything greater than 1 is left in n, it is a prime factor too.

Write your Python code, run it on the examples and submit it to hidden tests.