문화 접촉

16세기 초, 유럽 탐험대 한 무리가 유럽인을 한 번도 본 적 없는 여러 부족이 사는 섬에 도착했다.

섬 주민과 우호 관계를 맺기 위해 탐험대장은 길에서 만나는 각 부족의 우두머리에게 선물을 주려 한다. 대장은 보석처럼 보이는 유리 조각들이 길게 이어진 사슬을 가져왔다. 이 사슬을 소문자 영어 알파벳으로 이루어진 문자열 $s$로 본다. 각 문자는 해당 위치에 있는 유리 조각의 종류를 뜻한다.

탐험대는 사슬을 여러 조각으로 자르고, 만나는 부족의 우두머리마다 조각을 정확히 하나씩 준다. 대장은 아래 규칙에 따라 사슬을 나눈다.

• 각 조각은 연속된 유리 조각들로, 즉 $s$의 부분 문자열이다.
• 모든 유리 조각을 사용하며, 각 유리 조각은 정확히 하나의 조각에 포함된다.
• 모든 부족의 우두머리는 순서를 무시했을 때 같은 유리 조각 구성을 받는다. 즉, 유리 조각 종류마다 각 조각에 들어 있는 개수가 모두 같아야 한다.

부족의 수는 알 수 없으므로, 탐험대는 조각의 수가 가능한 한 많기를 원한다.

이 규칙을 어기지 않고 사슬을 최대 몇 개의 조각으로 나눌 수 있는지 구하라.

입력은 한 줄이며, 소문자 영어 알파벳으로 이루어진 비어 있지 않은 문자열 $s$가 주어진다. $s$의 길이는 $5 \cdot 10^6$을 넘지 않는다.

규칙을 어기지 않고 탐험대가 사슬을 나눌 수 있는 조각의 최대 개수를 한 개의 수로 출력하라.

첫 번째 경우에서 탐험대는 사슬 abbabbbab을 abb, abb, bab 조각으로 나눌 수 있다. 이때 각 부족의 우두머리는 종류 a 유리 조각 하나와 종류 b 유리 조각 두 개를 받는다.

두 번째 경우에서는 사슬을 두 조각 이상으로 나눌 수 없다.