Growth Points

Branchorama trees grow by an unusual rule. A young branchorama sapling is a thin stem with one leaf at the top, and that leaf contains a growth point. During a growing season, every growth point on the tree splits into several branches. After the season ends, each new branch has one leaf with a growth point at its tip. In the same year, every growth point on the same tree splits into the same number of branches; this number is the splitting factor for that year. The splitting factor may change from year to year.

The following picture shows a branchorama tree in Brown's orchard after growing for 3 years from a sapling.

As the picture suggests, branchorama trees tend to grow very densely. Brown therefore prunes overgrown branches every winter. The following picture shows a pruned branchorama tree.

A branchorama leaf is very large and good for photosynthesis, but leaves appear only at branch tips whose growth points remain intact. Therefore, pruning is done only enough for the tree to keep producing leaves.

Brown wants to know how many leaves each tree has. Counting leaves by hand is tedious, so given each year's splitting factor and the number of branches pruned that winter, compute the number of leaves left on the tree.

Each input line describes one branchorama tree.

A line starts with the tree's age a (1 <= a <= 20). It is followed by 2a integers separated by spaces. These integers list, for each year in order, the splitting factor and then the number of branches pruned that winter.

The last line contains a single 0. This line marks the end of input and must not be processed.

For each tree, output the number of leaves left on the tree on its own line. You may assume the number of leaves fits in a signed 32-bit integer.

The planted sapling starts with one branch and one leaf.