Background

Xiaoming is playing a game called “flipping coins”.

Problem Description

There are several coins on the table arranged in a row. We use * to represent heads and o to represent tails (the lowercase letter, not zero). For example, one possible situation is **oo***oooo. If we flip the two coins on the left at the same time, it becomes oooo***oooo. Now Xiaoming’s question is: given the initial state and the target state, and each move can only flip two adjacent coins at the same time, for a specific configuration, what is the minimum number of flips needed?

Input Format

Two strings of equal length, one per line, representing the initial state and the target state. The length of each line is less than $1000$.

The testdata guarantees that there is at least one way to transform from the initial state to the target state.

Output Format

One integer, the minimum number of operations.

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

5

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

1

Hint

source: Lanqiao Cup 2013 NOI Qualifier B Group, Problem H.

Translated by ChatGPT 5