SUBST1 - New Distinct Substrings

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

Output

For each test case output one number saying the number of distinct substrings.

Example

Input:
2
CCCCC
ABABA

Output:
5
9

Added by:Hoang Hong Quan
Date:2006-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Base on a problem in ByteCode06

hide comments
2010-02-25 15:40:53 [Rampage] Blue.Mary
Read the problem statement (especially the input section) CAREFULLY
2010-02-25 15:25:32 lccycc
What's the difference between this problem and 694?
2009-11-30 13:05:48 Ray
The time limit should be loosen. For Python(Psyco), it is nearly impossible to AC by Suffix Array.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.