Pyth, 12 11 bytes
}Q+M^^R2hQ2
I have a feeling that pyth can do better. 11 Bytes, you know, it's in comparison to other golfing languages a lot.
The algorithm is not different from the published answers and, consequently, the performance is not sufficient to calculate the two largest test values in less than 60 sec.
Commented version:
}Q # check whether the input value Q is within:
+M # the sums
^ 2 # of cartesian product with itself
^R2 # of squared
hQ # range of 0..Q