27ος ΠΔΠ B' Φάση Γυμνασίου
Άθροισμα τετραγώνων (twosqr)

Κάποιοι φυσικοί αριθμοί, όπως ο \(17\), μπορούν να γραφούν ως άθροισμα δύο τετραγώνων φυσικών αριθμών: \(17 = 1^2 + 4^2\). Άλλοι, όπως ο \(42\), δεν μπορούν να γραφούν σε αυτή τη μορφή. Κάποιοι φυσικοί αριθμοί, όπως ο \(25\), μπορούν να γραφούν σε αυτή τη μορφή με περισσότερους του ενός τρόπους: \(25 = 0^2 + 5^2 = 3^2 + 4^2\).

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI το οποίο θα διαβάζει κάποιους φυσικούς αριθμούς και να βρίσκει με πόσους διαφορετικούς τρόπους καθένας από αυτούς μπορεί να γραφεί ως άθροισμα δύο τετραγώνων φυσικών αριθμών.

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα twosqr.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν ακριβώς ένα φυσικό αριθμό \(T\) (\(1 \leq T \leq 1.000\)), το πλήθος των αριθμών που θα ακολουθήσουν. Ακολουθούν \(Τ\) γραμμές που κάθε μία περιέχει ακριβώς ένα φυσικό αριθμό \(N_i\) (\(0 \leq N_i \leq 1.000.000.000\)).

Aρχεία εξόδου

Τα αρχεία εισόδου με όνομα twosqr.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς \(Τ\) γραμμές, κάθε μία από τις οποίες περιέχει έναν ακέραιο αριθμό: το πλήθος των τρόπων με τους οποίους ο αντίστοιχος αριθμός \(N_i\) της εισόδου μπορεί να γραφεί ως άθροισμα δύο τετραγώνων φυσικών αριθμών.

Παράδειγμα αρχείων εισόδου - εξόδου

twosqr.in	twosqr.out
6 17 42 65 0 1025 203125	1 0 2 1 3 7

Μέγιστος χρόνος: \(1\) sec.