Largest Alliance Size

You are given n creatures, each with a given strength. Your task is to form the largest possible alliance such that every pair of creatures within the alliance is coprime. In other words, for every two distinct creatures with strengths a and b in the alliance, the greatest common divisor (gcd) must satisfy \(\gcd(a, b) = 1\).

Input constraints: The number of creatures, n, is provided along with their corresponding strengths. You can assume that n is small enough for a brute force solution to be feasible.

Example: For n = 6 and strengths 2 3 5 7 11 14, one optimal alliance is of size 5.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains an integer n, the number of creatures.
• The second line contains n space-separated integers representing the strengths of the creatures.

outputFormat

Output a single integer to stdout, indicating the size of the largest alliance in which every pair of creatures has coprime strengths.

6
2 3 5 7 11 14

5