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\left(1 \leq N \leq 10^{5}\right)~.
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_{i}\left(1 \leq i \leq n, 1 \leq A_{i} \leq 10^{5}\right)~.

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 \leq 20~;
• Subtask 2 (80% số test): Không có ràng buộc gì thêm.