You are given positive integer $k$. Find a graph $G$ that satisfies all of the following conditions:

• $G$ consists of $n$ nodes and $m$ edges
• $G$ is a directed acyclic graph
• $2 \le n \le 300,\ 1 \le m \le 400$
• Number of simple paths from vertex 1 to vertex $n$ is equal to $k$

Input format

• The single line contains one number $k\ (1≤k≤10^{18})$.

 Output format

• The first line contains two numbers $n$ and $m$.
• Next $m$ lines contain two numbers $u$ and $v$ that means there are directed edge from $u$ to $v$. $(1≤u≠v≤n).$

Please note that the sample is not the first test