Ước chung của hai số nguyên $x$, $y$ là tập hợp các số sao cho $x$, $y$ đều chia hết cho các số được gọi là ước chung. Ví dụ như $x=10$, $y=20$, thì các số $1,2,5,\ldots,10$ là ước chung của $10$ và $20$.

Yêu cầu: Cho dãy gồm $n$ số nguyên dương $A_1,A_2,\ldots,A_n$. Hãy đếm xem có bao nhiêu số là ước chung của tất cả các phần tử trong dãy số đã cho.

Input

Đọc từ file văn bản GCD.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương $n$;
• Dòng thứ hai chứa $n$ số nguyên $A_1,A_2,\ldots,A_n$.

Output

Ghi ra file văn bản GCD.OUT một số nguyên duy nhất là số lượng ước chung của dãy số.

Scoring

• Subtask 1 ($40\%$): $0 < 5\cdot 10^3$, $0 < A_i \leq 10^4$ với mọi $i$;
• Subtask 2 ($30\%$): $5\cdot 10^3 < N \leq 5\cdot 10^5$, $0<A_i \leq 10^6$ với mọi $i$;
• Subtask 3 ($30\%$): $5\cdot 10^3 < N \leq 5 \cdot 10^5$, $0<A_i \leq 10^{12}$ với mọi $i$.

Example

6
6 90 12 18 30 18

4