Description

小X有一张n个节点的图，每个节点有一个点权。但让小X感到生气的是，这张图上并没有任何的边，于是他决定钦点一些边。 小X喜欢gcd和合数，所以小X的钦点规则与 gcd（最大公约数）和合数有关。具体来说，对于2个点，如果它们点权的gcd 为合数，那么小X就会钦点它们之间连一条边。 小Y看到了小X稚的行为，决定把他批判一番。他知道小X热衷于连通块，因此他会删掉图中的一个点来使得剩余图中最大的连通块最小。 即将参加 NOIP2024 的你对这个问题很感兴趣，于是你想知道，在小Y操作之后，图中剩余的最大连通块的大小是多少。

Format

Input

Output

对于每组数据，输出一行一个整数，表示答案。

Samples

样例输入1

3
5 
8 4 12 18 9 
5 
36 20 84 45 231 
7 
100 200 300 400 500 600 700

样例输出1

2
3
6

大样例 connect2.in connect2.ans

Limitation

2s, 512MiB for each test case.