A. Новогодняя строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем строку из цифр 0, 2, 5 и/или 6 новогодней, если выполняется хотя бы одно из двух условий:

  • в ней есть вхождение строки 2026 в качестве непрерывной подстроки;
  • в ней нет вхождения строки 2025 в качестве непрерывной подстроки.

Например, строки 20252026, 21026, 20262026, 000 — новогодние. Строки 2025, 20256, 20252025, 000202500020226 не являются новогодними.

Вам задана строка $$$s$$$. Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):

  • выбрать любой символ строки $$$s$$$ и заменить его на 0, 2, 5 или 6 (по своему выбору).

Посчитайте минимальное количество операций, которое нужно выполнить, чтобы строка $$$s$$$ стала новогодней.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • в первой строке задано одно целое число $$$n$$$ ($$$4 \le n \le 20$$$) — количество символов в $$$s$$$;
  • во второй строке задана $$$s$$$ — последовательность из $$$n$$$ символов 0, 2, 5 и/или 6.
Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество количество операций, которое нужно выполнить, чтобы строка $$$s$$$ стала новогодней.

Пример
Входные данные
7
4
0000
4
2025
4
2026
8
20252026
8
20252025
9
202520256
9
202520265
Выходные данные
0
1
0
0
1
1
0
Примечание

Во втором примере из условия можно заменить $$$2$$$-й символ строки на 2. Тогда строка станет 2225.

В пятом примере из условия можно заменить $$$4$$$-й символ на 6. Тогда строка станет 20262025.

В шестом примере из условия можно заменить $$$8$$$-й символ на 6. Тогда строка станет 202520266.