Cho mảng ~A~ gồm ~N~ số nguyên dương. Với mỗi tập con khác rỗng của ~A~, định nghĩa trọng số của tập con này là ước chung lớn nhất của tất cả các phần tử trong tập con đó.

Hãy cho biết có bao nhiêu trọng số khác nhau tạo được từ các tập con khác rỗng của ~A~.

Dữ liệu

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~.

• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^5)~.

Kết quả

In ra số trọng số khác nhau tạo được từ các tập con khác rỗng của ~A~.

Ví dụ

Sample Input 1

5
1 2 3 4 5

Sample Output 1

5

Sample Input 2

5
2 6 9 4 24

Sample Output 2

7

Chấm điểm

• Subtask 1 (20% số test): ~N \le 20~

• Subtask 2 (80% số test): Không có ràng buộc gì thêm