lianhua - CITRUS!

⠀

You are an adventurer working for the futuristic corporation RoboCorp. Your current skill level is an integer $$$s$$$ in the range $$$[1, n]$$$, but you don't know its exact value. Your goal is to reach skill $$$\geq n$$$ by completing missions for RoboCorp, but each mission costs precious robocoins.

You can choose missions of any difficulty and any positive integer duration (in hours). However, the cost depends both on the new mission's length, and on how the new mission's difficulty compares to your most recent one.

Let $$$x$$$ be the difficulty of your most recent mission. If you want to undertake a new mission of difficulty $$$y$$$ and duration $$$l$$$:

If it is your first mission, or $$$y \leq x$$$, the cost is $$$l$$$ robocoins.
If $$$y \gt x$$$, the cost is $$$1000 + l$$$ robocoins.

Your skill improves only when you take on a mission whose difficulty exactly matches your current skill:

If $$$y = s$$$, then your skill increases by $$$l$$$.
Otherwise, your skill does not change.

After each mission, you still don't know your actual skill value.

You start with $$$10^6$$$ robocoins. Find a strategy (a sequence of missions) that does not exceed your budget and guarantees your skill becomes at least $$$n$$$, no matter what your initial skill was.

Input

The input contains a single line with an integer $$$n$$$ ($$$n = 4$$$ or $$$n = 250\,000$$$) — the target skill level (that is, by the end, your skill must be $$$\geq n$$$).

There are exactly $$$2$$$ tests in this problem (including the example). The example has $$$n = 4$$$, and the other test has $$$n = 250\,000$$$.

Hacks are not allowed in this problem.

Output

In the first line, print a single integer $$$k$$$ ($$$0 \leq k \leq 10^6$$$) — the number of missions you plan to complete.

Then, print $$$k$$$ lines. The $$$i$$$-th line must contain two integers $$$y$$$ and $$$l$$$ ($$$1 \leq y, l \leq 10^6$$$) — the difficulty and duration (in hours) of the $$$i$$$-th mission, respectively.

Note

In the example, your target skill is $$$n = 4$$$. You can use the following strategy:

Take a mission of difficulty $$$y = 1$$$ and duration $$$l = 4$$$. It's your first mission, so you pay $$$l = 4$$$ robocoins.
Take a mission of difficulty $$$y = 3$$$ and duration $$$l = 1$$$. The previous mission had difficulty $$$x = 1$$$, so since $$$y \gt x$$$, you pay $$$l + 1000 = 1001$$$ robocoins.
Take a mission of difficulty $$$y = 2$$$ and duration $$$l = 1$$$. Now $$$x = 3$$$, and since $$$y \leq x$$$, you pay $$$l = 1$$$ robocoin.
Take a mission of difficulty $$$y = 3$$$ and duration $$$l = 1$$$. Now $$$x = 2$$$, and since $$$y \gt x$$$, you pay $$$l + 1000 = 1001$$$ robocoins.

In total, you spend $$$2007$$$ robocoins, which is within your $$$10^6$$$-robocoin budget.

Now we verify that this strategy always works:

If your initial skill was $$$1$$$, after the first mission it becomes $$$5$$$.
If your initial skill was $$$2$$$, after the third mission it becomes $$$3$$$, and after the fourth mission it becomes $$$4$$$.
If your initial skill was $$$3$$$, after the second mission it becomes $$$4$$$.
If your initial skill was $$$4$$$, it stays $$$4$$$.

So no matter what your starting skill is, you end with skill $$$\geq n$$$.

Git Gud

Examples