题目背景

小 Z 对数论很感兴趣。

有一天，他遇到了一个难题……

题目描述

小 Z 得到了一个 \(N\)，要求输出：
- \(1 \sim N\) 之内的所有质数
- \(1 \sim N\) 之内所有数的最小值因数个数
- \(1 \sim N\) 之内所有数的因数个数
- \(1 \sim N\) 之内所有数的因数和

输入格式

一行，为一个整数 \(N\)。

输出格式

输出 \(4\) 行：
- \(1 \sim N\) 之内的所有质数
- \(1 \sim N\) 之内所有数的最小值因数个数
- \(1 \sim N\) 之内所有数的因数个数
- \(1 \sim N\) 之内所有数的因数和

样例 #1

不要提交

样例输入 #1

10

样例输出 #1

2 3 5 7 
0 1 1 2 1 1 1 3 2 1 
1 2 2 3 2 4 2 4 3 4 
1 3 4 7 6 12 8 15 13 18

提示

对于 \(100\%\) 的数据，\(2 \le N \le 5 \cdot 10^6\)