Задача Graph2021.
У графа Михайла є n садиб, розташованих по колу. Він хоче побудувати кілька підземних переходів між садибами, щоб пересуватися між ними швидше. Ви можете вибрати якесь число k, таке, що для кожної садиби вона буде з'єднана з k сусідніми ліворуч і з k садибами справа. Яке ж мінімальне k ви повинні обрати, щоб найкоротша відстань між будь-якими двома садибами була не більшою d ? Відстань між двома садибами вимірюється кількістю переходів, які потрібно зробити, щоб дістатися з однієї садиби до іншої.
Технічні умови. Програма Graph2021 читає з першого рядка ціле число t (1≤t≤10) – число наборів вхідних даних. Для кожного набору вхідних даних на новому рядку вводиться два цілих числа n і d (3 ≤ n≤ 1012, 1 ≤ d≤ 1012).
Програма виводить на пристрій стандартного виведення для кожного набору вхідних даних одне число в новому рядку – мінімальне k, що задовольняє умову задачі.
Приклад
|
Введення |
Виведення |
|
2 6 2 3 1 |
2 1
|
Коментар
У першому наборі вхідних даних якщо ми з'єднаємо кожну садибу з кожним із сусідів (тобто якщо k = 1), то для попадання в протилежну садибу потрібно буде здійснити 3 переходи (див. рисунок)
Якщо з'єднати кожну садибу з двома сусідами (к = 2) буде ситуація як на малюнку і знадобиться не більше двох переходів для потрапляння з будь-якої садиби до будь-якої.