在伯兰最近的一项研究中,科学家们发现古代伯兰有 n 个城市,由双向路径连接起来。任意两个城市仅由一条路径相连。没有一条道路能够将一座城市与它自身连接起来。根据一个众所周知的传统,道路网络的建设是不可能选择三个城市,从每个城市都可以直接到达另一个城市。也就是说,不存在与 3 一样长的周期。不幸的是,该路线图至今尚未保存。现在科学家们感兴趣的是古贝尔兰这个国家到底有多发达。帮助他们 - 找出该国最多有多少条道路。您还必须恢复任何可能的路线图。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100) — Berland 的城市数量。
输出
第一行必须打印数字 m — Berland 的最大道路数。然后打印 m 行,每行包含两个数字 - 给定道路连接的城市数量。城市用 1 到 n 的整数进行编号。如果解决问题有多种变体,请打印其中任意一种。
示例
输入 #1
3
输出 #1
2 1 2 2 3
输入 #2
4
输出 #2
4 1 2 2 3 3 4 4 1