Bit bərabərləşdirici

Verilmiş iki boş olmayan S və T sətirləri eyni uzunluqdadır. S sətiri 0, 1 və ? simvollarından, T isə yalnız 0 və 1 simvollarından ibarətdir. Məqsədiniz S sətirini minimal sayda hərəkətlə T sətirinə çevirməkdir. Hər bir hərəkətdə aşağıdakıları edə bilərsiniz:

1. S sətirindəki 0 simvolunu 1 simvoluna dəyişmək.

2. S sətirindəki ? simvolunu 0 və ya 1 simvoluna dəyişmək.

3. S sətirindəki istənilən iki simvolun yerlərini dəyişmək.

Məsələn, S = "01??00" və T = "001010" olduqda, S sətirini T sətirinə 3 hərəkətlə çevirmək mümkündür:

• Əvvəlcə S = "01??00"

• Hərəkət 1 - S[2] simvolunu 1 simvoluna dəyişmək. S sətiri "011?00" olacaq.

• Hərəkət 2 - S[3] simvolunu 0 simvoluna dəyişmək. S sətiri "011000" olacaq.

• Hərəkət 3 - S[1] simvolunu S[4] simvolu ilə dəyişmək. S sətiri "001010" olacaq.

• S indi T sətirinə bərabərdir.

Giriş məlumatları

Birinci sətir testlərin sayı t (t ≤ 200) ilə başlayır. Hər bir test iki sətirdən ibarətdir. Birinci sətir 0, 1 və ? simvollarından ibarət olan S sətiridir. İkinci sətir isə yalnız 0 və 1 simvollarından ibarət olan T sətiridir. Sətirlərin uzunluğu 100-dən çox deyil.

Çıxış məlumatları

Hər bir test üçün onun nömrəsini və S sətirini T sətirinə çevirmək üçün lazım olan minimal hərəkətlərin sayını çıxış edin. Əgər çevirmək mümkün deyilsə, -1 çıxış edin.

Nümunələr