Скажем, что последовательность строк t₁, ..., t_k является путешествием длины k, если для всех i > 1 t_i является подстрокой t_i - 1 строго меньшей длины. Например, {ab, b} является путешествием, а {ab, c} или {a, a} — нет.

Определим путешествие по строке s как путешествие t₁, ..., t_k, все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁, ..., u_k + 1, такие, что s = u₁ t₁ u₂ t₂... u_k t_k u_k + 1. К примеру, {ab, b} является путешествием по строке для abb, но не для bab, так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s.