Irrational Roots

Time limit1sMemory limit256 MB

Summary

Count how many of the n real roots of the given monic integer polynomial are irrational.

Level: Medium4 of 10
Topics: Number theory, Implementation
Solved: No attempts yet

Problem

You are given a natural number $n$ and integers $c_{n-1}, c_{n-2}, \dots, c_1, c_0$ . Consider the equation

$x^n + c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \dots + c_1x + c_0 = 0$

where $c_0 \neq 0$ , all $n$ roots of the equation are real, and every root $r$ satisfies $-10 \le r \le 10$ . The same value may occur as a root more than once.

Write a program that counts how many of the $n$ roots are irrational. Roots are counted with multiplicity, so an irrational root that occurs three times counts as 3.

Input

The first line contains $n$ . ( $1 \le n \le 8$ )

The second line contains $c_{n-1}, c_{n-2}, \dots, c_1, c_0$ in that order, separated by single spaces.

Output

Print the number of irrational roots on one line.

Examples3

Example 1
Input
```
6
12 -12 -454 -373 3754 1680
```
Expected output
```
2
```
Example 2
Input
```
1
-5
```
Expected output
```
0
```
Example 3
Input
```
2
0 -2
```
Expected output
```
2
```