У вас есть цифровые часы, на которых всегда отображаются \(n\) цифр. Каждая цифра может быть любым целым числом от \(0\) до \(9\), поэтому часы могут показывать целые числа от \(0\) до \(10^n-1\). Часы будут показывать лидирующие нули, если число меньше, чем \(10^{n-1}\).
Вы хотите сделать так, чтобы часы показывали \(0\), за минимальное число операций. За одну операцию вы можете сделать одно из следующего:
- уменьшить число на часах на \(1\), или
- поменять местами две цифры (вы можете выбрать, цифры на каких позициях менять местами, они не обязательно должны быть соседними).
Определите, какое минимальное число операций необходимо сделать, чтобы часы показывали \(0\).
Выходные данные
Для каждого набора входных данных выведите наименьшее количество операций, чтобы установить на часах значение \(0\).
Примечание
В первом примере оптимально просто уменьшить число \(7\) раз.
Во втором примере можно сначала поменять местами первую и последнюю цифры, а затем уменьшить число на \(1\).
В третьем примере часы уже показывают \(0\), поэтому можно ничего не делать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
007
4
1000
5
00000
3
103
4
2020
9
123456789
30
001678294039710047203946100020
|
7
2
0
5
6
53
115
|