Perfect Square Pair Sum

Medium

Given a non-negative integer c, determine whether there exist two non-negative integers a and b such that the sum of their squares equals c . In other words, return true if there is a valid pair (a, b) where a² + b² = c, and false otherwise. Note that a and b can be equal (for example, both could be 0 or the same positive integer), and the order of the pair does not matter (i.e., if (a, b) is valid, then (b, a) is also considered the same valid representation). The challenge lies in efficiently searching through the space of possible integer pairs to verify whether such a decomposition exists for the given value c .

Example 1

Input

c = 5

Output

true

Explanation

The number 5 can be expressed as 1² + 2² = 1 + 4 = 5. Therefore, we return true.

Example 2

Input

c = 3

Output

false

Explanation

There is no pair of non-negative integers (a, b) such that a² + b² = 3. The closest possibilities are 1² + 1² = 2 and 1² + 2² = 5, neither of which equals 3.

Example 3

Input

c = 4

Output

true

Explanation

The number 4 can be expressed as 0² + 2² = 0 + 4 = 4. Therefore, we return true.

Constraints

0 ≤ c ≤ 2³¹ - 1