eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Контрольна точка

Контрольна точка

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Ви приймаєте участь в гонках на 2D решітці, стартуючи з початку координат (0, 0) та рухаючись до фінішу (M, N), де М та N - натуральні числа, 0 < MN. На шляху є контрольна точка, що не співпадає ані з точкою старту, ані з точкою фінішу. Вона має координати (m, n), причому 0mM та 0nN. Вам слід пройти контрольну точку перш ніж досягнете фінішу. Довжина найкоротшого шляху до фініша дорівнює T = M + N.

З кожної точки Ви можете перейти в одну з чотирьох найближчих сусідніх точок, зберігаючи при цьому постійну швидкість. Але оскільки Ви не бажаєте програти гонку, то кожний раз будете продовдувати рух або вправо, або вгору.

Хоча існує багато способів дійти до фінішу через контрольну точку, гонка вважається простою, оскільки знайти найкоротший маршрут завжди легко. Щоб зробити гонку більш цікавою, ми змінимо правила. Замість того, щоб просто дістатися до фінішу (M, N), гонщикам пропонується самостійно обрати координати фінішу (x, y) та контрольної точки таким чином, щоб до фінішу існувало рівно S різних найкоротших шляхів.

Наприклад, розглянемо для S = 4 два варіанти розташування фінішу та контрольної точки.

Розташуємо контрольну точку в (1, 3), а фініш в (2, 3). Існує 4 шляхи від старту до контрольної точки. Від контрольної точки до фінішу можна дістатися лише єдиним шляхом, зробивши при цьому мінімальну кількість кроків. Таким чином усього існує 4 різних найкоротших шляхів, довжина яких дорівнює T = 2 + 3 = 5. Однак існує кращий варіант вибору контрольної точки та фінішу.

Розташуємо контрольну точку в (1, 1), а фініш в (2, 2). Існує два шляхи від старта до контрольної точки. Аналогічно існує в точності два шляхи дістатися від контрольної точки до фінішу. Що в цілому дає 4 різні найкоротші шляхи. Довжина цих шляхів дорівнює T = 2 + 2 = 4.

Будучи гонщиком Хакер Капа, Вам слід вирішити де розташувати контрольну точку і фініш, щоб не програти. За заданим значенням S знайдіть найменше можливе T, яке досягається при усіх можливих місцях розташування контрольної точки та фінішу, щоб існувало в точності S різних найкоротших шляхів від старту до фінішу, що проходять через контрольну точку.

Вхідні дані

Перший рядок містить кількість гонок R (R 20), в яких Ви приймаєте участь. Далі йдуть R рядків, кожний з яких описує гонку одним значенням S (1S10000000). Рядки між собою розділяються символом "\n".

Вихідні дані

Для кожної гонки у окремому рядку вивести її номер, як наведено у прикладі, а також найменшу можливу довжину найкоротшого шляху T.

Приклад

Вхідні дані #1
5
4
5
12
14
1
Вихідні дані #1
Case #1: 4
Case #2: 6
Case #3: 6
Case #4: 9
Case #5: 2
Джерело Facebook Hacker Cup 2012 Round 1