DCEPC13G - Can you solve it

One day, Palak challenged Rishabh with a problem to test his skills. She gave him 2 hrs. But Rishabh had a meeting to attend with someone important. Can you solve the problem on his behalf?

Given an array A of size N, find the maximum size subset such that every 2 elements are coprime.

Two numbers x and y are said to be coprime when gcd(x, y) = 1, where gcd is the greatest common divisor.

Input

There is a single integer N in first line which denotes size of array.
The second line contains N space separated integers which are the elements of the array A.

Output

Print the size of the largest subset such that every 2 elements is coprime.

Constraints

1 <= N <= 100
1 <= Ai <= 100

Example

Input:
3
1 13 26

Output:
2

Added by:dce coders
Date:2015-03-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA

hide comments
2016-10-09 11:39:49 |RAMSDEN|
Wrong testcases!! :(
Don't waste time solving this problem.

Last edit: 2016-10-09 12:02:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.