Towers

The number n and a sequence of n integers are given. Consider all possible cyclic shifts of this sequence. Sort them lexicographically and print the sum of greatest common prefixes of adjacent shifts in this order.

Input

Input contains no more than 200 test cases. Each test case consists of two lines. The first line contains the number of magic towers n (1 ≤ n ≤ 50000). The second line contains n integers in the range from 0 to 100 - the given sequence.

The last test case contains n = 0 and is not processed.

Output

For each test case print in a separate line the required sum.

Examples