E. Раскодирование
Ограничение времени
2 секунды
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
В интернете появился новый сервис. К сожалению, у него нет документации. Опытным путем от сервера была получена строка s. Однако некоторые символы в этой строке закодированы и чтобы получить настоящий ответ, нужно эту строку раскодировать несколько раз. Поскольку документация на сервис отсутствует, для дальнейших экспериментов нужно определить какое максимальное число раз можно нетривиальным образом раскодировать эту строку. Процедура раскодирования следующая: нужно найти все подстроки вида «&XY;» (без кавычек), где X и Y— большие или маленькие шестнадцатеричные цифры и заменить их одновременно на символ с ASCII-кодом 16X+Y (у каждой подстроки свой). Раскодирование называется тривиальным, если подстрок такого вида нет.
Формат ввода
На входе дана строка s длины 1≤|s|≤300000, состоящая из символов с кодами от 33 до 126 включительно.
Формат вывода
В единственной строке выведите максимальное число последовательных нетривиальных раскодирований исходной строки.
Пример 1
Ввод
Вывод
&26;
1
Пример 2
Ввод
Вывод
&&32;&36;;&fF;
2
Пример 3
Ввод
Вывод
&&30;&30;;&3b&3B;
2
Пример 4
Ввод
Вывод
&Ff&3b;
2
Пример 5
Ввод
Вывод
&he;llo
0
Примечания
В процессе раскодирования могут появляться символы с кодами меньше 33 или больше 126. Символ "&" имеет ASCII код 0x26=38, а символ ";" имеет ASCII код 0x3b=59.