В один не самый прекрасный вечер Валере было очень скучно. Чтобы немного себя развлечь, Валера нашел следующее занятие.
Он взял белый квадратный клетчатый лист бумаги, состоящий из n × n клеток. После этого он стал закрашивать белые клетки листа одну за другой в черный цвет. Всего он закрасил m различных клеток этого листа. Поскольку у Валеры была какая-то предрасположенность ко всему квадратному, его заинтересовал следующий вопрос — после какого хода впервые на листке можно найти черный квадрат со стороной 3. Однако Валера не знает ответ на этот вопрос и поэтому просит Вашей помощи.
От Вас требуется найти минимальный номер хода, после которого на клетчатом листке образовался хотя бы один квадрат черного цвета со стороной 3 или определить, что такого хода нет.
Выходные данные
В единственной строке выведите ответ на задачу — минимальный номер хода, после которого на листе образуется черный квадрат со стороной 3. Если такого хода не существует, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 11
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
3 3
4 1
|
10
|
|
2
|
4 12
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
4 2
4 1
3 1
|
-1
|