Resting at the country house of Petya's grandmother, Peter and Bob decided to build a secret headquarters for his espionage organization. To accommodate all the spy equipment they need a room area of exactly s square meters. The headquarters walls were build of material, found in grandmother's shed. It was wood planks, each of length of exactly one meter. Choosing the form of a room, Bob remembered his last geometry lesson where he studied the right triangles. So he offered to build a headquarters in the form of this figure. And in this case they can easily calculate its area and make sure that it is required.

But it turned out that there is no saw, so its not possible to cut the boards. Vasya and Petya have to build a headquarters in the form of a right triangle, with all sides expressed in integer number of meters. He wondered how many such triangles exist. Triangles that have the same length of the sides, but differ by their order, are considered the same.

Input

One integer s (1 ≤ s ≤ 10000) - the required headquarters area.

Output

Print one integer - the number of different possible headquarters plans with the area of s square meters.