For two given positive integers $x$ and $y$, if there exists a prime number $p$ such that $x \cdot p = y$, then the positive integers $x$ and $y$ are said to be prime-related.

For a given set $S$ consisting of $n$ positive integers, if $S_1$ is a subset of $S$ such that no two positive integers in $S_1$ are prime-related, then $S_1$ is called a non-prime-related subset of $S$. The maximum non-prime-related subset of $S$ is the non-prime-related subset with the largest number of elements.

The maximum non-prime-related subset problem asks to find the size of the maximum non-prime-related subset for a given set $S$ of $n$ positive integers.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each test case consists of two lines: The first line contains a positive integer $n$, representing the number of positive integers in set $S$. The second line contains $n$ positive integers, which are the elements of set $S$.

Output

For each test case, output a single line in the format "Case #T: ans", where $T$ is the test case number (starting from 1) and $ans$ is the answer.

Constraints

Examples

Input 1

3
5
2 4 6 8 10
5
2 3 5 7 11
9
2 3 4 5 6 7 8 9 10

Output 1

Case #1: 3
Case #2: 5
Case #3: 5