Вирівнювач бітів

Дано дві непорожні рядки 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: змінити 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.

Приклади