Longest chain

There is a list of positive integers. Find the size of its largest subset, that can be arranged in a chain in a such way, that among each two neighbour elements one divides another.

Specifications

Input

First line of input contains the quantity of tests T (1 ≤ T ≤ 35). Each of the next T lines contains the quantity of elements N (1 ≤ N ≤ 17) and N positive integers, each number will be between 1 and 10⁹ inclusively.

Output

Output T lines of the form “Case #A: B”, where A is the number of test (beginning from 1), B is the desired number for this test case.

Problem information

Time Limit: 10 seconds
Memory Limit: 64 MB
Balls for the passed test: 10
Complexity: 33% 10/15

Example

Example input

2
3 1 2 3
5 2 3 4 5 6

Example output

Case #1: 3
Case #2: 4

← Bell numbers

Problems

Lines →