## Uốn vuông

View as PDF

Points: 1.10 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSPC 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~12~ là độ dài của sợi dây ngắn nhất để có thể bị uốn cong thành hình tam giác vuông có các cạnh là số nguyên.

Chúng ta có thể kể ra một số ví dụ khác như: ~24~: ~(6~, ~8~, ~10)~, ~30~: ~(5~, ~12~, ~13)~, ~36~: ~(9~, ~12~, ~15)~, ~40~: ~(8~, ~15~, ~17)~, ~48~: ~(12~, ~16~, ~20)~.

Sợi dây độ dài ~20~ không thể bị uốn thành một tam giác vuông có cạnh nguyên theo bất cứ cách nào.

Một số sợi dây với độ dài khác lại có thể uốn thành tam giác vuông có cạnh nguyên theo nhiều cách khác nhau, ví dụ ~120~: ~(30~, ~40~, ~50)~, ~(20~, ~48~, ~52)~, ~(24~, ~45~, ~51)~.

Gọi độ dài của dây là ~L~, hỏi có bao nhiêu giá trị ~L \leq N~ để có thể tạo ra duy nhất một tam giác vuông có cạnh nguyên?

#### Input

Gồm nhiều test, mỗi test nằm trên một dòng là số nguyên ~N \leq 20000000~.

#### Output

Ứng với mỗi test, in ra trên một dòng số lượng số ~L \leq N~ mà chỉ có thể tạo ra duy nhất ~1~ tam giác vuông.

#### Sample Input

12
30


#### Sample Output

1
3