У Николая есть строка \(s\) четной длины \(n\), состоящая из латинских букв 'a' и 'b'. Позиции букв пронумерованы от \(1\) до \(n\).
Он хочет изменить свою строку таким образом, чтобы в любом её префиксе четной длины было поровну букв 'a' и 'b'. Для этого Николай может производить следующую операцию любое количество раз (возможно, нулевое): выбрать позицию в своей строке и заменить букву на этой позиции на другую (то есть заменить букву 'a' на букву 'b' или заменить букву 'b' на букву 'a'). Использовать какие-либо другие буквы, кроме 'a' и 'b', Николай не может.
Префиксом строки \(s\) длины \(l\) (\(1 \le l \le n\)) называется строка \(s[1..l]\).
Например, для строки \(s=\)«abba» существует два префикса чётной длины. Первый из них — это \(s[1\dots2]=\)«ab», второй из них — это \(s[1\dots4]=\)«abba». Оба префикса содержат одинаковое количество букв 'a' и 'b'.
Ваша задача — посчитать минимальное количество операций, которое должен сделать Николай со строкой \(s\), чтобы в любом ее префиксе четной длины строки стало поровну букв 'a' и 'b'.
Выходные данные
В первую строку выведите минимальное количество операций, которые Николай должен произвести со строкой \(s\), чтобы в любом префиксе ее префиксе четной длины стало поровну букв 'a' и 'b'.
Во вторую строку выведите строку Николая после проведения им всех операций. Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере Николай должен произвести две операции. Например, он может заменить первую букву 'b' на букву 'a' и заменить последнюю букву 'b' на букву 'a'.
Во втором примере не нужно заменять никакие буквы, так как в любом префиксе четной длины исходной строки содержится поровну букв 'a' и 'b'.