Уже в детском саду Саше понравилась одна девочка. Поэтому он захотел подарить ей рисунок и привлечь её внимание.
В качестве рисунка он решил нарисовать клетчатый квадрат \(n \times n\), в котором закрашены некоторые клетки. Но закрашивать клетки сложно, поэтому он хочет закрасить как можно меньше клеток. При этом он хочет, чтобы хотя бы в \(k\) диагоналях была закрашена хотя бы одна клетка. Обратите внимание, что всего квадрат \(n \times n\) имеет \(4n - 2\) диагонали.
Помогите маленькому Саше влюбить в себя девочку и скажите, какое минимальное количество клеток ему нужно закрасить.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество клеток, которые нужно закрасить.
Примечание
На картинках снизу чёрным цветом отмечены закрашенные клетки, фиолетовым цветом отмечены все диагонали.
В первом наборе входных данных можно закрасить \(2\) клетки так, чтобы \(4\) диагонали содержали хотя бы одну закрашенную клетку:
В третьем наборе входных данных можно закрасить \(6\) клеток так, чтобы все \(10\) диагоналей содержали хотя бы одну закрашенную клетку:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3
|
2
2
6
5
4
6
2
|