Даны две непустые строки S и T одинаковой длинны. S содержит символы '0', '1' и '?', в то время как T содержит только '0' и '1'. Вам следует преобразовать S в T за минимальное количество ходов. За каждый ход можно:
изменить '0' в S на '1'
изменить '?' в S на '0' или '1'
поменять местами любые два символа в S
Например, пусть S = "01??00" и T = "001010". Можно преобразовать S в T за 3 хода:
Изначально S = "01??00"
Ход 1 – изменить S[2] на '1'. S станет "011?00"
Ход 2 – изменить S[3] на '0'. S станет "011000"
Ход 3 – поменять S[1] с S[4]. S станет "001010"
S теперь равно T
Первая строка содержит количество тестов t (t ≤ 200). Каждый тест состоит из двух строк. Первой является строка S, состоящая из '0', '1' и '?'. Второй является строка T, состоящая из '0' и '1'. Длины строк не превосходят 100.
Для каждого теста вывести его номер и наименьшее количество ходов, необходимых для преобразования S в T. Если преобразование невозможно, вывести -1.