Георгий — кот, поэтому он очень любит играть. Больше всего ему нравится играть с имеющимся у него массивом положительных целых чисел b. В процессе игры, Георгий изменяет массив специальными операциями. Обозначим текущий массив Георгия как b1, b2, ..., b|b| (запись |b| обозначает текущую длину массива). Тогда одна операция — это последовательность действий:
- Выбрать два различных индекса i и j (1 ≤ i, j ≤ |b|; i ≠ j) таких, что bi ≥ bj.
- Получить число v = concat(bi, bj), где concat(x, y) — число, полученное добавлением числа y в конец десятичной записи числа x. Например, concat(500, 10) = 50010, concat(2, 2) = 22.
- Добавить в конец массива число v. Длина массива увеличится на один.
- Удалить из массива элементы с индексами i и j. Длина массива уменьшается на два, а элементы перенумеровываются от 1 до текущей длины массива.
Георгий долго играл со своим массивом b и в итоге получил из него массив, состоящий из ровно одного числа p. Теперь Георгий хочет узнать: какое максимальное количество чисел мог содержать массив b первоначально? Помогите ему, найдите это число. Учтите, что первоначально массив мог содержать только положительные целые числа.
Выходные данные
Выведите целое число — какое максимальное количество элементов мог содержать массив b первоначально.
Примечание
Рассмотрим тестовые примеры:
- Изначально массив b мог быть равен {5, 9, 5, 5}. Последовательность операций, которую совершил Георгий, могла быть: {5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}.
- Изначально массив b мог быть равен {1000000000, 5}. Обратите внимание, в массиве b не может быть нулей.
- Изначально массив b мог быть равен {800, 10, 1}.
- Изначально массив b мог быть равен {45}. Он не мог быть равен {4, 5}, поскольку из этого массива за одну операцию можно получить только массив {54}.
Обратите внимание, что числа в результирующем массиве могут быть очень большими.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9555
|
4
|
|
2
|
10000000005
|
2
|
|
3
|
800101
|
3
|
|
4
|
45
|
1
|
|
5
|
1000000000000001223300003342220044555
|
17
|
|
6
|
19992000
|
1
|
|
7
|
310200
|
2
|