Background

Description

对于x，如果不存在一个小于x的正数y使得x和y的最大公约数大于1，则我们把x称为QAQ数，反之则不是QAQ数。 现在给你一个整数的序列，你的任务是计算序列中QAQ数的和。

Format

#input 输入有多组测试数据。 对于每组测试数据： 第一行为一个整数 N(1≤N≤1000)。 第二行为 N个整数，每个整数的范围都是1到1000。

Output

对于每组测试数据，输出QAQ数的和。

Samples

3
5 6 7
1
10

12
0

Limitation

1s, 1024KiB for each test case.