#P1607A. Linear Keyboard

    ID: 242 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>implementationstrings*800

Linear Keyboard

No submission language available for this problem.

Description

You are given a keyboard that consists of 2626 keys. The keys are arranged sequentially in one row in a certain order. Each key corresponds to a unique lowercase Latin letter.

You have to type the word ss on this keyboard. It also consists only of lowercase Latin letters.

To type a word, you need to type all its letters consecutively one by one. To type each letter you must position your hand exactly over the corresponding key and press it.

Moving the hand between the keys takes time which is equal to the absolute value of the difference between positions of these keys (the keys are numbered from left to right). No time is spent on pressing the keys and on placing your hand over the first letter of the word.

For example, consider a keyboard where the letters from 'a' to 'z' are arranged in consecutive alphabetical order. The letters 'h', 'e', 'l' and 'o' then are on the positions 88, 55, 1212 and 1515, respectively. Therefore, it will take 58+125+1212+1512=13|5 - 8| + |12 - 5| + |12 - 12| + |15 - 12| = 13 units of time to type the word "hello".

Determine how long it will take to print the word ss.

The first line contains an integer tt (1t10001 \leq t \leq 1000) — the number of test cases.

The next 2t2t lines contain descriptions of the test cases.

The first line of a description contains a keyboard — a string of length 2626, which consists only of lowercase Latin letters. Each of the letters from 'a' to 'z' appears exactly once on the keyboard.

The second line of the description contains the word ss. The word has a length from 11 to 5050 letters inclusive and consists of lowercase Latin letters.

Print tt lines, each line containing the answer to the corresponding test case. The answer to the test case is the minimal time it takes to type the word ss on the given keyboard.

Input

The first line contains an integer tt (1t10001 \leq t \leq 1000) — the number of test cases.

The next 2t2t lines contain descriptions of the test cases.

The first line of a description contains a keyboard — a string of length 2626, which consists only of lowercase Latin letters. Each of the letters from 'a' to 'z' appears exactly once on the keyboard.

The second line of the description contains the word ss. The word has a length from 11 to 5050 letters inclusive and consists of lowercase Latin letters.

Output

Print tt lines, each line containing the answer to the corresponding test case. The answer to the test case is the minimal time it takes to type the word ss on the given keyboard.

Samples

Sample Input 1

5
abcdefghijklmnopqrstuvwxyz
hello
abcdefghijklmnopqrstuvwxyz
i
abcdefghijklmnopqrstuvwxyz
codeforces
qwertyuiopasdfghjklzxcvbnm
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
qwertyuiopasdfghjklzxcvbnm
abacaba

Sample Output 1

13
0
68
0
74