4C decided to give his girlfriend a gift. His friend loves flowers and so he decided that he would give her all kinds of flowers. There is only one problem, each branch of tree has only one unique flower and the flower at every branch is different from flower of every other branch. 4C wants to know the number of different flowers that he can give to his girlfriend.

The task is simple. You have to tell the number of branches in a suffix substring branched tree. The question in your mind is, what the hell is this?? Let me tell you. It is similar to trie. You have to report number of branches in a trie created by a string. To create a trie, you have to take each possible suffix of string and then insert it in trie.

See the example figure for clarification.

Example:

Let the string be abczbcz

The suffix substrings bcz, cz, and z get superimposed on bczbcz, czbcz, zbcz respectively.

Constraints:

All the characters are between 'a' to 'z'

Length of string <= 1000000

Test cases = 10

Problem Setter - Satyarth