Nauuo — девочка, которая любит играть в шахматы.
Однажды она сама придумала игру, для которой нужны \(n\) шахматных фигур на доске \(m\times m\). Строки и столбцы пронумерованы целыми числами от \(1\) до \(m\). Обозначим клетку на пересечении \(r\)-й строки и \(c\)-го столбца как \((r,c)\).
Цель игры — расставить на доске \(n\) шахматных фигур, пронумерованных целыми числами от \(1\) до \(n\). Пусть \(i\)-я фигура находится в клетке \((r_i,\,c_i)\). Должно соблюдаться следующее правило: для каждой пары фигур \(i\) и \(j\) должно выполняться \(|r_i-r_j|+|c_i-c_j|\ge|i-j|\). Здесь \(|x|\) обозначает абсолютное значение числа \(x\).
Вскоре Nauuo поняла, что иногда она не сможет найти решение игры, ведь доска может быть слишком маленькой.
Она хочет найти самую маленькую шахматную доску, на которой можно правильно расставить \(n\) фигур.
Nauuo также интересует, как следует расставлять фигуры на доске. Можете ли вы помочь ей?
Выходные данные
Выведите одно целое число — минимальное значение \(m\), где \(m\) это длина стороны подходящей шахматной доски.
В \(i\)-й из следующих \(n\) строк выведите два целых числа \(r_i\) и \(c_i\) (\(1\le r_i,c_i\le m\)) — координаты \(i\)-й шахматной фигуры.
Если существует несколько подходящих ответов, вы можете вывести любой.
Примечание
В первом примере вы не можете расставить фигуры на доске \(1\times1\) без нарушения описанных правил. Но вы можете расставить их на доске \(2\times2\) следующим образом:
Во втором примере вы не можете расставить фигуры на доске \(2\times2\) без нарушения описанных правил. Например, если вы расставите их следующим образом:
то \(|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1\), \(|1-3|=2\), \(1<2\), а также \(|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2\), \(|1-4|=3\), \(2<3\), это нарушает правило.
Однако вы можете расставить их на доске \(3\times3\) следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
2
1 1
1 2
|
|
2
|
4
|
3
1 1
1 3
3 1
3 3
|