Сложность: 15%
У графа Михаила есть усадеб расположенных по кругу. Он хочет построить несколько подземных переходов между усадьбами, чтобы перемещаться между ними быстрее. Вы можете выбрать какое-то число , такое, что для каждой усадьбы она будет соединена с соседними усадьбами слева и усадьбами справа. Какое же минимальное вы должны выбрать, чтобы кратчайшее расстояние между любыми двумя усадьбами было не больше ? Расстояние между двумя усадьбами измерятеся в количестве переходов, которые нужно сделать, чтобы добраться из одной усадьбы в другую.
Входные данные
Первая строка содержит одно целое число () — число наборов входных данных. Для каждого набора входных данных на новой строке вводится два целых числа и (, ).
Выходные данные
Для каждого набора входных данных выведите одно число - минимальное удовлетворяющее условию. Числа разделяйте переводами строк.
Система оценки
В задаче 20 тестов, за каждый из которых вы получите 5 баллов.
Решения, корректно работающие при получат не менее 25 баллов.
Решения, корректно работающие при получат не менее 70 баллов.
STDIN | STDOUT |
2 6 2 3 1 | 2 1 |
Примечание
В первом наборе входных данных если мы соединим каждую усадьбу с каждым из соседей (т.е. если ), то для попадания в противоположную усадьбу нужно будет совершить 3 перехода (см. рисунок)
Если соединить каждую усадьбу с двумя соседями () будет ситуация как на рисунке и потребуется не больше двух переходов для попадания из любой усадьбы в любую.
Во втором наборе данных мы просто соединяем все усадьбы ().