J. Batch Please!
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the premier episode of Hell's Kitchen – UTPC Edition, teams are competing to make meals for their hungry customers. It's the red team vs. the blue team; the red team is making pizzas, while the blue team is making burgers.

You are on the blue team, and you just made a burger – but you've botched it! The burger layers are all wrong! You've got a list of orders for burgers, and you'd like to know how you might be able to fix your burger.

Formally, let's represent a burger as a string, where each character represents a layer. For example, "pblt" might represent a burger consisting of a patty on bacon on lettuce on tomato (in that order).

You have a list of correct burgers, and you want to modify your botched burger to create these target burgers. In one operation, you may:

  1. Remove one topping from the top of your burger (for example, "pblt" $$$\rightarrow$$$ "blt")
  2. Add one topping to the top of your burger (for example, "pblt" $$$\rightarrow$$$ "epblt")
  3. Remove one topping from the bottom of your burger (for example, "pblt" $$$\rightarrow$$$ "pbl")
  4. Add one topping to the bottom of your burger (for example, "pblt" $$$\rightarrow$$$ "pbltm")
In order to figure out the easiest way to fix your burger, please determine how many operations are required to build each target burger out of the original botched burger.
Input

The first line contains a single integer $$$N\ (1 \le N \le 10^3)$$$, the number of target burgers.

The second line contains a string representing the original botched burger $$$S\ (1 \le |S| \le 10^3)$$$.

The next $$$N$$$ lines each contain a single string representing the target burgers $$$T_1,...,T_N\ (1 \le |T_i| \le 10^3)$$$.

All burgers are strings consisting only of the lowercase letters $$$a$$$ through $$$z$$$.

Output

Output $$$N$$$ lines, where line $$$i$$$ contains a single integer denoting the minimum number of operations required to build the $$$i^\text{th}$$$ target burger.

Examples
Input
3
pblt
blt
pbpb
blbl
Output
1
4
4
Input
1
pblbtllpbltt
pbpbltpbpt
Output
14
Note

In the first test case:

  1. "pblt $$$\rightarrow$$$ blt" requires a single operation.
  2. "pblt $$$\rightarrow$$$ pbl $$$\rightarrow$$$ pb $$$\rightarrow$$$ pbp $$$\rightarrow$$$ pbpb" requires four operations.
  3. "pblt $$$\rightarrow$$$ pbl $$$\rightarrow$$$ bl $$$\rightarrow$$$ blb $$$\rightarrow$$$ blbl" requires four operations.