寻找只因数

题目描述

只因数是一种非常稀有的质数，不是所有的质数都叫只因数

举个例子：

37397就是一个只因数，它也是一个质数

我们从它的最右边砍下它的只因屁股，留下的部分是3739，它依然是个一个质数

我们再从它的最右边砍下它的只因翅膀，留下的部分是373，它仍然是个一个质数

我们再从它的最右边砍下它的只因腿，留下的部分是37，它居然是个一个质数

我们再从它的最右边砍下它的只因脖子，留下的部分是3，它好像还是一个质数

当它只剩下最后1位我们就不能再砍啦，再砍它一下它就要爆炸了。

这样的数就是只因数，是不是太酷啦。

请你帮忙求出所有n位的只因数

输入格式

一行一个正整数 $n$。

输出格式

按顺序输出长度为 $n$ 的只因数,每行一个。

样例 #1

样例输入 #1

5

样例输出 #1

23333
23339
23399
23993
29399
31193
31379
37337
37339
37397
59393
59399
71933
73331
73939

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 8$。

上面是题目，我猜测$\text{O(n)}$就会爆炸。

求思路，最好不要是丝绸之路。