Description

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

Format

Input

第一行为一个整数 N(1≤N≤1000)。 第二行为 N个整数，每个整数的范围都是1到1000。

Output

输出QAQ数的和。

Samples

6
571 425 635 479 977 802 

2027

Limitation

1s, 1024KiB for each test case.