Ignacio and Ines really like science. Luckily they live in Nlogonia, where as everyone knows there are N science museums. Both Ignacio and Ines have the next N Saturdays free, so they have agreed on a schedule to visit a different science museum each of these days.

Ignacio is quite stingy, so every Saturday he will tell Ines that he has forgotten to bring the money to pay the museum's entrance fee, and will therefore ask her to pay for him. Ines always does so, and because she knows him well she also knows that unless she asks for her money back, he will never pay up. In fact, Ines is certain that even if she asks Ignacio for her money back, he will only accept to pay if the cumulative debt is a multiple of 100, because otherwise he will argue that he has no change to pay exactly, and will thus pay nothing at all.

This being the situation, every Sunday if the cumulative debt is a multiple of 100 Ines will go to Ignacio's house to claim her money, and because he'll have no excuse left, he will pay without any type of protest. Of course he doesn't like this, but he is comforted by the idea that if the cumulative debt after visiting the N museums is not a multiple of 100, Ines shall not claim the last part of her money.

Ines would like to know how many times she will have to go to Ignacio's house to ask for her money. In order to calculate this, she can provide a list of the prices of the entrance fees to the N science museums in Nlogonia, in the order that she and Ignacio are going to visit them.

Input

Each test case is described using two lines. The first line contains a single integer number N, indicating the number of science museums in Nlogonia (1 ≤ N ≤ 100). The second line contains N integers P_i representing the prices of the entrance fees to the different museums, in the order in which they are going to be visited (1 ≤ P_i ≤ 100 for i = 1, ..., N). The end of the input is signalled by a line containing the number -1.

Output

For each test case, you should print a single line containing an integer number, representing the number of times Ines is going to have to go by Ignacio's house to ask for her money.

Example

Input:
3
50 50 50
5
50 100 100 100 100
9
25 50 75 100 25 50 75 100 25
5
35 45 20 22 33
3
100 100 100
-1

Output:
1
0
2
1
3