The number \textbf{n} and a sequence of \textbf{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. \InputFile Input contains no more than \textbf{200} test cases. Each test case consists of two lines. The first line contains the number of magic towers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}). The second line contains \textbf{n} integers in the range from \textbf{0} to \textbf{100} - the given sequence. The last test case contains \textbf{n} = \textbf{0} and is not processed. \OutputFile For each test case print in a separate line the required sum.