题目描述

现在小明拿到了一个数字 $n$ ，他想知道 $n!$ （ $n$ 的阶乘）的质因数分解结果是多少？请你按照要求输出。

输入格式

输入一行，包含一个整数 $n$ 。

输出格式

输出若干行，按照从小到大的顺序输出 $n!$ 的每个质因子和对应的次幂，两个数用空格隔开。

10

2 8
3 4
5 2
7 1

提示

$2 \le n \le 12$ 。