Carrier

After a lot of chilling, Pikachu is determined to build his carrier. The sole purpose of his carrier is to count the number of times a carry is generated when a group of numbers are simultaneously added together. For example, when the 5 numbers 999, 999, 999, 999 and 999 are added together, the carrier will return 3.

You are his friend and you have no idea why Pikachu got this new whim. And of course, Pikachu is bad at maths and asked you to figure out the solution.

More formally, you will be given an array $A$ of $N$ integers. You have to find the number of times a carry will be generated if you simultaneously add them together.

Input

The first line of the input contains a single integer $N$ ($1 ≤ N ≤ 100$). The next line contains $N$ space separated integers ($0 ≤ A_i ≤ 10^{18}$).

Output

Print a single integer which is the output of the carrier.

Samples

Input	Output
5 999 999 999 999 999	3
The following table shows the logic of the carrier for the 2nd sample input:

Input	Output
12 999 999 999 999 999 999 999 999 999 999 999 999	4

Input	Output
5 1 2 3 2 1	0