Substrings

Πόσες διακριτές υποσυμβολοσειρές (substrings) έχει μια δεδομένη συμβολοσειρά ~S~;

Για παράδειγμα, αν ~S~ = "~abc~", το ~S~ έχει ~7~ διακριτές υποσυμβολοσειρές: {"", "~a~", "~b~", "~c~", "~ab~", "~bc~", "~abc~"}. Σημειώστε ότι η κενή συμβολοσειρά και το ίδιο το ~S~ θεωρούνται υποσυμβολοσειρές ης ~S~.

Από την άλλη πλευρά, εάν ~S~ = "~aaa~", το ~S~ έχει μόνο ~4~ διακριτές υποσυμβολοσειρές: {"","~a~", "~aa~", "~aaa~"}.

Είσοδος

Η πρώτη γραμμή του αρχείου εισόδου περιέχει το ~N~, τον αριθμό των περιπτώσεων δοκιμής. Για κάθε δοκιμαστική περίπτωση, ακολουθεί μια γραμμή που περιέχει την ~S~, μια συμβολοσειρά από ~1~ έως ~1000~ αλφαριθμητικούς χαρακτήρες.

Έξοδος

Η έξοδος σας αποτελείται από μία γραμμή ανά περίπτωση, δίνοντας τον αριθμό των διακριτών υποσυμβολοσειρών της ~S~.

Προσπαθήστε να γράψετε ένα αποτελεσματικό πρόγραμμα.

Παράδειγμα

input

2
abc
aaa

output

7
4