题目背景

我曾如此地接近。

我恨她。

...

我这次一定要坚持到底。

不能再逃跑了。

题目描述

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$，你将不会得到额外分数。