Summer is coming!

When you travel, you always plan ahead. You have shortlisted N cities to travel. Each city has distinct integer id from 1 to N. Each city also has a satisfaction score associated with it. If you travel to a city you will get the satisfaction score. Your “Happiness Score” is the sum of all the satisfaction scores from all the cities you’ve travelled to.

You have a passion for numbers – especially prime numbers. You want to know how many possible unique prime numbers you can get as “Happiness Score” by visiting any subset (possibly some or all) of the N cities.

**Input Format**

First line will be an integer denoting number of cities. Second line will have satisfaction score SiSi for all the cities from 1 to N.

### Notes

- 1<=N<=18
- 1<=Si<=100000
- A prime number is a natural number greater than 1 which has no positive divisors other than 1 and itself.

**Output Format**

Output should be an integer number denoting how many possible `Happiness Scores`

you can get which are prime numbers.

**Sample Input**

```
3
3 2 6
```

**Sample Output**

```
4
```

**Explanation**

You can achieve “Happiness Scores” 3, 2, (3+2), (3+2+6) , where all of them are prime numbers. Here 2, 3 , 5, 11 are prime numbers.

**Solution**