Triangle

Interview

Time limit2sMemory limit1024 MB

Summary

Count the right triangles with integer sides (unordered) whose area is exactly S, where S is at most 10,000.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Statement

Petya and Vasya are resting at Petya's grandmother's dacha and decided to build a secret headquarters for their spy organization. Their equipment needs a room with an area of exactly $S$ square meters. They must build the walls from scrap materials they found in the grandmother's shed. The materials are wooden boards, each exactly one meter long.

Vasya remembered right triangles from their last geometry lesson and proposed building the headquarters in that shape. The area of a right triangle is easy to compute, so they can check it against $S$ .

There is no saw, so the boards cannot be cut. The headquarters must be a right triangle whose sides are all whole numbers of meters. Triangles with the same side lengths in a different order count as the same triangle.

Count the building plans whose area is exactly $S$ square meters.

Input

The input file contains one integer $S$ ( $1 \le S \le 10,000$ ), the required area of the headquarters.

Output

Print one integer, the number of building plans whose area is exactly $S$ square meters.

Examples2

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
6
```
Expected output
```
1
```