У Ashish есть бинарная строка \(s\) длины \(n\), которую он хочет отсортировать в неубывающем порядке.
Он может выполнять следующую операцию:
Найдите минимальное количество операций, необходимых для того, чтобы отсортировать строку в неубывающем порядке. Можно доказать, что всегда можно отсортировать заданную бинарную строку не более чем за \(n\) операций.
Первая строка содержит одно целое число \(t\) \((1 \le t \le 1000)\) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число \(n\) \((1 \le n \le 1000)\) — длину бинарной строки \(s\).
Вторая строка каждого набора входных данных содержит бинарную строку \(s\) длины \(n\), содержащую только символы \(0\) и \(1\).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(1000\).
Для каждого набора входных данных выведите следующее:
В первом наборе входных данных строка уже отсортирована в неубывающем порядке.
Во втором наборе входных данных мы можем выполнить следующую операцию:
\(\underline{1}\) \(0\) \(\underline{1}\) \(\underline{0}\) \(\underline{0}\) \(\rightarrow \) \(\underline{0}\) \(0\) \(\underline{0}\) \(\underline{1}\) \(\underline{1}\)
В третьем наборе входных данных мы можем выполнить следующую операцию:
\(0\) \(0\) \(\underline{1}\) \(0\) \(\underline{0}\) \(\underline{0}\) \(\rightarrow \) \(0\) \(0\) \(\underline{0}\) \(0\) \(\underline{0}\) \(\underline{1}\)
3 7 0011111 5 10100 6 001000
0 1 4 1 3 4 5 1 3 3 5 6
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач