题目描述

小蓝最近迷上了杨辉三角, 杨辉三角是一个无限向下递增的数字三角形。下图展示了杨辉三角的前 $11$ 行：

我们定义函数 $f(i)$ 表示数字 $i$ 在杨辉三角中出现的次数（其中 $i \geq 2$）。

现在，给定一个正整数 $n$（$n \geq 2$），请你完成以下任务：

• 对于所有满足 $2 \leq x \leq n$ 的整数 $x$，计算出对应的 $f(x)$；
• 将所有具有相同 $f(x)$ 值的数字归为一组；
• 统计并输出每个不同的 $f(x)$ 值出现了多少次。

输入格式

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

输出格式

输出若干行。第 $i$ 行包含两个整数 $v_i, c_i$，用一个空格分隔，表示使得函数 $f(x) = v_i$ 的个数为 $c_i$。按照 $v_i$ 从小到大的顺序输出。

5

1 1
2 3

解释 #1

$x$ 的取值范围是 $[2, 5]$，其中 $f(2) = 1$，$f(3) = f(4) = f(5) = 2$，即值为 $1$ 出现了 $1$ 次，值为 $2$ 出现了 $3$ 次。

数据范围

• 对于 $20\%$ 的评测用例，$2 \leq n \leq 100$；
• 对于 $40\%$ 的评测用例，$2 \leq n \leq 1000$；
• 对于 $60\%$ 的评测用例，$2 \leq n \leq 10,000$；
• 对于所有评测用例，$2 \leq n \leq 100,000$。