URI Online Judge | 1747

# Even Distribution

Timelimit: 1

Endre has lots of nieces and nephews. Once a year, he takes some of them on a trip to an archipelago where a boat company operates two-way services between some pairs of islands. Since Endre and the children can fly and return directly to or from any of the islands, any trip can be described as a non-empty sequence i1, i2,..., in of islands, such that each pair of consecutive islands ij and ij+1 have a boat service between them. The first and the last islands of a trip may or may not be the same island, and the islands may be visited more than once during the trip.

Each island in the archipelago produces a different peculiar variety of candy, and greets its visitors by giving each arriving group a fixed number of pieces of candy. Endre does not like candies himself, but the children eat them all almost instantly. To avoid fights, each time the group arrives to an island and receives candies, he evenly distributes them among the children.

You may wonder how Endre always manages to evenly distribute the candies they receive in each island. Well, the answer is actually very simple. Each year, the travel agency sends him the trip plan (the sequence i1, i2,..., in ) beforehand. Since he wants to travel with as many of his nieces and nephews as possible, he calculates the maximum number k of kids he can take on the trip without violating the rule about the even distribution of candy. Notice that each trip plan uniquely determines the number of kids to take.

This has been going on for years, and each time Endre ends up taking a different number of kids on the trip. He would like to know how many different numbers of kids he can take on a trip, that is, the number of integers k such that there is a trip plan for which he ends up taking k kids on the trip. Right now Endre is very busy preparing this year’s trip. Can you help him with the answer?