The task is simply stated. Given an integer n (3 < n < 10^(9)), find the length of the smallest list of [*perfect squares*](https://en.wikipedia.org/wiki/Square_number) which add up to n. Come up with the best algorithm you can; you'll need it!
Examples:
sum_of_squares(17) = 2  17 = 16 + 1 (4 and 1 are perfect squares).
sum_of_squares(15) = 4  15 = 9 + 4 + 1 + 1. There is no way to represent 15 as the sum of three perfect squares.
sum_of_squares(16) = 1  16 itself is a perfect square.
Time constraints:
5 easy (sample) test cases: n < 20
5 harder test cases: 1000 < n < 15000
5 maximally hard test cases: 5 * 1e8 < n < 1e9
```if:java
300 random maximally hard test cases: 1e8 < n < 1e9
```
```if:c#
350 random maximally hard test cases: 1e8 < n < 1e9
```
```if:python
15 random maximally hard test cases: 1e8 < n < 1e9
```
```if:ruby
25  random maximally hard test cases: 1e8 < n < 1e9
```
```if:javascript
100 random maximally hard test cases: 1e8 < n < 1e9
```
```if:crystal
250 random maximally hard test cases: 1e8 < n < 1e9
```
```if:cpp
Random maximally hard test cases: 1e8 < n < 1e9
```
from math import sqrt


def sum_of_squares(n):
    n_sqrt = int(sqrt(n))

    if n == n_sqrt * n_sqrt:
        return 1

    div, mod = divmod(n, 4)
    while mod == 0:
        div, mod = divmod(div, 4)
    if (div * 4 + mod) % 8 == 7:
        return 4

    for i in range(1, n_sqrt + 1):
        temp = n - i * i
        temp_sqrt = int(sqrt(temp))
        if temp == temp_sqrt * temp_sqrt:
            return 2

    return 3
from math import sqrt


def sum_of_squares(n):
    n_sqrt = int(sqrt(n))

    if n == n_sqrt * n_sqrt:
        return 1

    div, mod = divmod(n, 4)
    while mod == 0:
        div, mod = divmod(div, 4)
    if (div * 4 + mod) % 8 == 7:
        return 4

    for i in range(1, n_sqrt + 1):
        temp = n - i * i
        temp_sqrt = int(sqrt(temp))
        if temp == temp_sqrt * temp_sqrt:
            return 2

    return 3