Minh đang chơi một trò chơi “lật đồng xu”.

Trên bàn đặt một hàng gồm một số đồng xu. Ta dùng * biểu thị mặt ngửa, dùng o biểu thị mặt sấp (là chữ cái o thường, không phải số không), ví dụ một trạng thái có thể là **oo***oooo, nếu lật đồng thời hai đồng xu bên trái thì nó trở thành oooo***oooo. Bây giờ câu hỏi của Minh là: nếu đã biết trạng thái ban đầu và trạng thái đích cần đạt được, mỗi lần chỉ được lật đồng thời hai đồng xu kề nhau, thì với một tình huống cụ thể, cần lật ít nhất bao nhiêu lần?

Dữ liệu vào

Hai dòng là hai xâu ký tự có độ dài bằng nhau, lần lượt biểu thị trạng thái ban đầu và trạng thái đích cần đạt được, mỗi dòng có độ dài nhỏ hơn $1000$.

Dữ liệu đảm bảo luôn tồn tại ít nhất một phương án đi từ trạng thái ban đầu đến trạng thái đích.

Dữ liệu ra

Một số nguyên, biểu thị số bước thao tác ít nhất.

Ví dụ 1

Input

**********
o****o****

Output

5

Ví dụ 2

Input

*o**o***o***
*o***o**o***

Output

1

Ghi chú

Nguồn: Lanqiao Cup 2013 vòng tỉnh, bảng B bài H