提示: 欢迎访问OurACM平台。
Problem 1603 Checkers II

Accept: 182    Submit: 496
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

It is easy for us to solve "Checkers" using the formula . Now the problem has a little changed .

Figure 1:

Oaiei’s new problem is showed as follows :

  1. The chessboard is a straight line which has N lattices.
  2. There are two kinds of chesses and one empty lattice in the chessboard.
  3. The initial state will be given arbitrarily.
  4. There are two possible ways of moving :
    • a chess can move directly to the adjacent empty lattice
    • a chess can jump over one lattice into the next empty lattice
  5. The end state will be given arbitrarily too.
  6. The state is in the following format:
    • @ represents the first kind of chesses
    • # represents the second kind of chesses
    • & represents the empty lattice
    • @ and # have the same number
  7. When you change the initial state into the end state, the game is over.

Your task is coming. Give you the initial state and the end state, and you should calculate the minimum move steps you have done to change the initial state into the end state.

Input

The first line is an integer T(T<=35), means the number of test cases. Following T lines, each line contain two strings A and B which have the same size N(N is a positive odd integer which is less than 21). A indicates the initial state and B indicates the end state.

Output

For each test case, print the integer number which indicting the minimum move steps.

Sample Input

1 ##&@@ @@&##

Sample Output

8

Hint

The one of solutions in the example with the minimum move steps is shown as follows:


represents ‘#’
represents ‘@’
represents ‘&’

Source

FOJ月赛-2008年5月

Submit  Back  Status  Discuss