Длиннейшая цепочка

Дан список целых положительных чисел. Найдите размер его максимального подмножества, которое можно выстроить в цепочку таким образом, чтобы среди любых двух соседних элементов один делился на другой.

Технические условия

Входные данные

Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 35). Каждая из следующих T строк содержит количество элементов множества N (1 ≤ N ≤ 17) и N целых положительных чисел, каждое – от 1 до 10⁹ включительно.

Выходные данные

Выведите T строк вида “Case #A: B”, где A – номер теста (начиная с 1), B – искомая величина для данного теста.

Информация о задаче

Лимит времени: 10 секунд
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 33% 10/15

Пример

Пример входных данных

2
3 1 2 3
5 2 3 4 5 6

Пример выходных данных

Case #1: 3
Case #2: 4

← Числа Белла

Список задач