Rohan is going to take part in the Invento with this friend Mohan. Rohan got the various chocolate bars of different length on his birthday. Rohan wants to share his chocolate bars with Mohan, but the problem is that Rohan can break the chocolate in integer length only and he wants that both of them get the equal length pieces. Due to this restriction, he is able to share only some of his chocolate bars with Mohan.

Given the number of chocolate bars and length of each bar, you need to find out the number of chocolate bars which Rohan can share with Mohan.

Input Format

First line contains integer n, number of chocolate bars
Second line contains n space separated integers denoting the length of chocolate bars

Output Format

Output the single integer which is answer to the problem

Constraints

• 1 ≤ n ≤ 100000
• 1 ≤ Length of chocolate bar ≤ 10⁹
• Rohan can break a chocolate bar only once