最大两两互质小组

题目描述

从给定 n 个位置中选择尽可能多的位置，使任意两个被选位置上的整数互质。即使数值相同，不同位置仍是不同候选，但不能重复选择同一位置。

输入格式

第一行输入 n，满足 1≤n≤18。第二行输入 n 个正整数，每个不超过10^6。

输出格式

输出最多可选择的位置数量。

样例

输入

1
6

输出

1