KMS-QT is one of the most romantic couples of NSIT. A monster kidnapped QT. In order to release her he demanded a task to be solved by his boyfriend KMS. Here is the task :-

Given an array of size n , find number of distinct values that are obtained by performing gcd of all elements of all possible subarrays that can formed in the given array .

For Example :- Let array be [2,4] Then all possible subarrays are [2],[4],[2,4] . The GCD values of the given subarrays are 2,4,2 . The number of distinct GCD values are 2 i.e. (2,4). Hence, 2 should be the answer .

INPUT FORMAT

n is given in the first line of each test file. It is followed by n integers on next lines representing the array.

OUTPUT FORMAT

This should only contain answer to the problem .

CONSTRAINTS

1<=N<=100000
1<=A[i]<=1000000