問題文


ロボてりーは文字列 を持っています。 は最初、空文字列です。
ロボてりーは がともに空文字列になるまで、以下の操作を上から順に行うことを繰返します。

  • のうち、空文字列でないものを選ぶ。(両方空文字列でない場合はどちらを選んでも良い。)
  • 選んだ文字列の先頭の要素を削除する。
  • 削除された要素を として、 の末尾に を加える。

操作の繰返しを終えた後の のスコアを、以下の条件を満たす の連続部分文字列の長さの最大値とします。

条件: 文字列全体が広義単調増加である。

ただし、文字列全体が広義単調増加とは、文字列内の任意の 要素 について、 よりも右にあるならばアルファベット順で が成り立つことをさします。例えば、 "aaa""cxyz" は広義単調増加ですが、 "ea" は広義単調増加ではありません。

ロボてりーは忙しいので、代わりに のスコアとしてあり得るものの最大値を求めてあげてください。

  

制約


  • は英小文字からなる

  

入力


入力は以下の形式で標準入力から与えられます。


  

出力


答えを出力してください。

  

入力例1


abc
arc

出力例1


5

最終的な としてあり得る文字列として、例えば "aabcrc" がありますが、この文字列のスコアは であり、この入力においての最適解です。  
 

入力例2


x
a

出力例2


2

"xa" とするとスコアは ですが、 "ax" とするとスコアは になります。  
 

入力例3


edcba
zyx

出力例3


2

 

入力例4


hibiki
chan

出力例4


5

提出


Go (1.14)