Remarkable Primes

Time limit

Memory limit

4 MB

Problem

Subin loves prime numbers and enjoys exploring them. Recently, one number caught her attention: 7331.

The number 7331 is prime. More surprisingly, 733, 73, and 7 are also prime. In other words, every prefix formed by taking the first 1, 2, 3, and 4 digits from the left is prime. Subin calls such a number a remarkable prime.

Given N, find every N-digit remarkable prime.

Input

The first line contains an integer N (1 ≤ N ≤ 8).

Output

Print all N-digit remarkable primes in ascending order, one per line.