[Celeste-B] Center of the Earth

> 我曾如此地接近。 > 我**恨**她。 > > ... > 我这次一定要坚持到底。 > 不能再逃跑了。

Madeline 来到了一座神龛前，这座神龛布满尘埃，四周还都是不明所以的符号。 通过 Madeline 强大的观察能力，她发现这些符号其实对应着一个个冲刺顺序，按照一定顺序冲刺就相当于输入一个密码，只有输入特定的密码才能点亮神龛获得水晶之心。 多年之后，当 Madeline 回忆她的登山之旅时，她已经不记得密码是什么了，只记得密码长度为 $3$，并且每一位密码有 $n$ 种可能。她还知道，在她输入的密码中，任意两位与标准密码相符就能点亮神龛获得水晶之心。 今天，Madeline 又回到了这座神龛前，她希望使用最少的输入密码次数来保证能获得这颗水晶之心，你能帮帮她吗？

第一行一个整数 $n$，表示每一位密码有多少种可能。

第一行输出一个整数 $k$，表示你给出的方案中输入密码的次数。 接下来 $k$ 行，输出每次尝试的密码。

2

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

样例不是最优解，只是对输出的一个示例。 **请务必输出方案，否则可能会遇到未知错误** 共有三个测试点： 测试点 $1$($10$pts) : $n=2$ 测试点 $2$($20$pts) : $n=100$ 测试点 $3$($70$pts) : $n=1000$ 对于每组数据我们采取如下评分方式： - 若 $k > 5000000$ ，你的输出过大，你将无法得到任何分数。 - 否则： - 若给出的方案无法保证能点亮神龛，或者方案本身是错误的，则按照如下规则评分： - 若 $k$ 小于最小次数，不给分。 - 否则，若 $k$ 等于最小次数，则给出该测试点 $10\%$ 的分数。 - 否则，若你的 $k$ 是最小次数的 $q$ 倍，你将得到这个测试点 $\frac{1}{10*q}$ 的分数。 - 否则，你的方案可以保证点亮神龛，则按照如下规则评分： - 首先得到 $10\%$ 的基础分。 - 接着，令最小次数为 $p$，你将得到如下额外分数： - $k=p$，你将得到 $90\%$ 的额外分数。 - $p<k<=1.5p$，你将得到 $50+\frac{1.5p-k}{0.5p}*40\%$ 的额外分数。 - $1.5p<k<=2p$，你将得到 $20+\frac{2p-k}{0.5p}*30\%$ 的额外分数。 - $k>2p$，你将不会得到额外分数。