Candy's Candy

Time limit1sMemory limit128 MB

Summary

Count the ways to split F flavors' counts into equal-size packs, some single-flavor and at least one containing all flavors, with each flavor having a flavored pack.

Level: Hard8 of 10
Topics: Number theory, Math, Implementation, Combinatorics
Solved: No attempts yet

Problem

Candy has candy in $F$ different flavors, and she wants to make several packs to sell them. Each pack is one of two kinds:

flavored pack: contains candy of a single flavor;
variety pack: contains candy of every flavor.

Candy calls a packing nice if it satisfies all of the following conditions:

Every piece of candy is placed in exactly one pack.
Every pack, of either kind, contains at least $2$ pieces of candy.
Every pack, of either kind, contains the same number of pieces of candy.
Within each variety pack, the number of pieces of each flavor is the same.
There is at least one variety pack.
For every flavor, there is at least one flavored pack of that flavor.

Candy wonders how many different nice packings she can make. Two nice packings are considered different if they differ in the number of flavored packs, in the number of variety packs, or in the number of pieces of candy per pack.

Input

The input consists of several test cases. Each test case is given on two lines. The first line contains an integer $F$ ( $2 \le F \le 10^5$ ), the number of flavors. The second line contains $F$ integers $C_i$ ( $1 \le C_i \le 10^9$ ), the number of pieces of candy of each flavor.

The last test case is followed by a line containing a single $0$ .

Output

For each test case, output on its own line the number of different nice packings that can be made according to the rules above.

Examples3

Example 1

Input

3
15 33 21
2
1 1
2
2 2
2
3 3
3
1000000000 1000000000 1000000000
0

Expected output

Example 2
Input
```
2
6 6
0
```
Expected output
```
3
```
Example 3
Input
```
3
30 42 18
0
```
Expected output
```
7
```