第3回 ドワンゴからの挑戦状 予選

B - ニコニコレベル


Time limit時間制限 : 2.525sec / Memory limitメモリ制限 : 252.525MB

配点 : 300

問題文

ニコニコ文字列とは、250 回以上繰り返した文字列のことをいいます。たとえば 25252525 や空文字列はニコニコ文字列ですが、123225 はニコニコ文字列ではありません。

ある文字列 S がその連続した部分文字列として含む最長のニコニコ文字列の長さを Sニコニコレベル といいます。 たとえば 52525, 25025, 12151 のニコニコレベルはそれぞれ 4, 2, 0 です。

ニワンゴくんは 0 から 9 の数字と ? からなる文字列 T を持っており、それぞれの ? を好きな数字に置き換えることで、数字のみからなる文字列 T' を作ろうとしています。ニワンゴくんが作ることのできる文字列 T' のニコニコレベルの最大値を求めて下さい。

制約

  • 1 ≦ |T| ≦ 10^5
  • T の文字は 0 から 9 の数字か ? のいずれかである。

入力

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

T

出力

ニワンゴくんが作ることのできる文字列 T' のニコニコレベルの最大値を 1 行で出力せよ。


入力例 1

12??567890

出力例 1

4

? を前から順に 52 に置き換えて 1252567890 とすると、2 文字目から 5 文字目が 2525 となり、ニコニコレベル 4 の文字列を作ることができます。


入力例 2

65?5?4?

出力例 2

2

入力例 3

314159265358979

出力例 3

0

25 が全く現れない文字列はニコニコレベル 0 になります。


入力例 4

2???5????

出力例 4

8

入力例 5

52

出力例 5

0

Submit提出する