Longest

In a box, Peter has some ticket, each with a number written on it. He finds the following game interesting: First, he selects a ticket from the box and puts it on the table. Then he tries to find a number in the box that has some common prime factor with the last number on the table. If it is possible, then he puts it next to the last number, and tries again. If he fails to select an appropriate number, the game is over. He wants to know the length $M$ of longest possible number sequence, that can be selected from the box according to the rules. Help him to compute this maximal length!

For example, if his tickets are: 2, 4, 7, 14, 3, 21, 49, then the sequences 2, 4, 14, 7, 21, 3 and 4, 2, 14, 21, 3 and 3, 21, 49, 7, 14, 4, 2 are possible outcomes of the game, and for this case, we can conclude that $M=7$.

Input specification

The number of tickets $N$ in the first line, then the space separated list of tickets $C_i\ \ (i=1\ldots N)$ in the next one.

Output specification

A single line with the maximal possible length $M$.

Constraints

$1\le N \le 20$
$1\le C_{i} \le 100000$

Sample input 1

1. 7
2. 1 3 5 7 11 13 17

Sample output 1

1. 1

Sample input 2

1. 7
2. 2 4 8 16 32 64 128

Sample output 2

1. 7

Sample input 3

1. 16
2. 1 124 34 45 43 22221 65537 1023 2 4 8 16 32 3 9 27

Sample output 3

1. 13

Sample input 4

1. 20
2. 7 29 81 32 25 63 37 53 3 63 71 11 25 84 17 70 3 4 56 20

Sample output 4

1. 14