Leghosszabb

Péternek egy dobozban van néhány cédulája, mindegyiken egy-egy pozitív egész szám. A következő játékot eszelte ki velük: Kezdő lépésként választ egy cédulát a dobozból és leteszi az asztalra. Ezután a megpróbál a maradék cédulákból olyat választani, melynek a legutoljára asztalra tett számmal van közös prímtényezője. Ha nem sikerül megáll, összeszámolja az asztalon levő cédulákat és visszateszi azokat a dobozba. Ha sikerül akkor leteszi azt az asztalra az utolsó mellé és megint próbálkozik. Segítsünk neki megállapítani, hogy maximálisan hány cédulát tud egy menetben a dobozából egymás mellé tenni ($M$).

Például, ha a dobozában levő számok: 2, 4, 7, 14, 3, 21, 49, akkor a 2, 4, 14, 7, 21, 3 és a 4, 2, 14, 21, 3 és a 3, 21, 49, 7, 14, 4, 2 három lehetséges kimenetele a játéknak, így $M=7$ ebben az esetben.

Bemenet specifikáció

Az első sorban a cédulák $N$ száma van, a másodikban pedig a cédulákon szereplő $C_i\ \ (i=1\ldots N)$ számok, szóközzel elválasztva.

Kimenet specifikáció

Az output egyetlen sorába a maximálisan választható cédulák $M$ száma kerül.

Korlátok

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

1. példa bemenet

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

letöltés szöveges állományként

1. példa kimenet

1. 1

letöltés szöveges állományként

2. példa bemenet

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

letöltés szöveges állományként

2. példa kimenet

1. 7

letöltés szöveges állományként

3. példa bemenet

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

letöltés szöveges állományként

3. példa kimenet

1. 13

letöltés szöveges állományként

4. példa bemenet

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

letöltés szöveges állományként

4. példa kimenet

1. 14

letöltés szöveges állományként