e-olymp
Задачі

Найдовший ланцюжок

Найдовший ланцюжок

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

Вхідні дані

Перший рядок містить кількість тестів T (1T35). Кожен з наступних T рядків містить кількість елементів множини N (1N17) та N цілих додатних чисел, кожне – від 1 до 109 включно.

Вихідні дані

Виведіть T рядків вигляду “Case #A: B”, де A – номер тесту (починаючи з 1), B – шукана величина для даного тесту.

Ліміт часу 10 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані
2
3 1 2 3
5 2 3 4 5 6
Вихідні дані
Case #1: 3
Case #2: 4