E. Crossroads
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Michael Rypka is eating at Torchy's as part of a group of $$$n$$$ friends, and they are sat evenly spaced around a circular table labeled from $$$1$$$ to $$$n$$$ going clockwise around the circle. After getting their tacos and sauces, they realized everyone had a lot of the wrong items. So, they all need to exchange items. Specifically, each person needs to exchange items directly with every other person at the table. However, they want to avoid cross contamination, so no two pairs of people can exchange items if the direct line between each pair intersects. In a given round, any two people can agree to exchange items given it meets the conditions above. Please help Michael figure out the minimum number of rounds it will take his friends to exchange all their items, and provide a series of exchanges they can conduct to do so.

Input

The input will contain a single integer $$$n$$$ ($$$2 \leq n \leq 10^3$$$) indicating how many people are sitting around the table.

Output

The first line should indicate a single integer $$$r$$$ denoting the minimum number of rounds that it takes Michael and his friends to exchange all their items. For each round, output a single integer $$$k$$$ denoting the number of exchanges that will occur in that round followed by $$$k$$$ lines each containing two space separated integers $$$i$$$ and $$$j$$$ indicating that friends $$$i$$$ and $$$j$$$ agreed to exchange in this round.

Note: if there is an exchange between friends $$$i$$$ and $$$j$$$, no other exchange in that round should include either $$$i$$$ or $$$j$$$. Additionally, not every friend needs to make an exchange in every round.

Examples
Input
2
Output
1
1
1 2
Input
4
Output
4
1
3 1
2
3 2
1 4
1
4 2
2
4 3
1 2