We have two strings A and B which are permutations of the same set of characters. We need to change these strings to obtain two identical strings by performing the following operations:

1. swap two consecutive characters of a string
2. swap the first and the last characters of a string

The operation can be performed on either string. Return the minimum number of moves that we need in order to obtain two equal strings?

Constraints

1 < length(A) = length(B) ≤ 2,000

All the input characters are between 'a' and 'z'

The count of each distinct character in A is identical to the count of the same character in B.

Input

First line: String A.

Second line: String B.

Output

Minimum number of moves.

Example

Input:
aab
baa

Output:
1