Given a string s. We call any non-empty string t good, if it is a substring of s and has 4 non-overlapping occurrences in s. Your task is to find the number of different good strings.
Contains one string s (1≤length of s≤105) — given string. It is guaranteed that all letters are lowercase English alphabet.
Print one integer — the number of different good strings.