Даны две непустые строки S и T одинаковой длинны. S содержит символы 0, 1 и ?, в то время как T содержит только 0 и 1. Вам следует преобразовать S в T за минимальное количество ходов. За каждый ход можно:

1. изменить 0 в S на 1
2. изменить ? в S на 0 или 1
3. поменять местами любые два символа в S

Например, пусть S = "01??00" и T = "001010". Можно преобразовать S в T за 3 хода:

• Изначально S = "01??00"
• Ход 1 - изменить S2 на 1. S станет "011?00"
• Ход 2 - изменить S3 на 0. S станет "011000"
• Ход 3 - поменять S1 с S4. S станет "001010"
• S теперь равно T

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

Первая строка содержит количество тестов t (t ≤ 200). Каждый тест состоит из двух строк. Первой является строка S, состоящая из 0, 1 и ?. Второй является строка T, состоящая из 0 и 1. Длины строк не превосходят 100.

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

Для каждого теста вывести его номер и наименьшее количество ходов, необходимых для преобразования S в T. Если преобразование невозможно, вывести -1.