B. Rayo loves DNA Repair (Orange)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Raphael and Rayo are trying to fix a corrupted genetic sequence for the team!

They have an initial DNA string $$$a$$$ and a target DNA string $$$b$$$.

To transform string $$$a$$$ into string $$$b$$$, they must use the following techniques:

  • The Ninja Shadow Swap: Raphael has mastered certain connection points $$$(i, j)$$$ in the DNA. He can swap the characters at these positions in string $$$a$$$ as many times as he wants for free (0 operations);
  • The Katana Strike (Replacement): If a character cannot be moved into the correct spot via swaps, Raphael must use his katana to slice out the old character and replace it with a new one of his choice, Each replacement costs 1 operation.
Trying to figure it out

Find the minimum number of replacement operations needed to make string $$$a$$$ match string $$$b$$$. If the transformation is impossible, print -1.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — denotes the number of test cases.

for each test case:

The first line is two strings $$$a$$$ and $$$b$$$ ($$$1 \le |a| , |b| \le 10^5$$$) — denotes the starting DNA and the target DNA, they are guaranteed to only have lowercase letters.

The second line is an integer $$$M$$$ — denotes the number of pairs that can be swapped for free.

The next $$$M$$$ lines contains two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le |a|$$$) — denotes the positions in string $$$a$$$ that can be swapped for free.

It is guaranteed that the sum of $$$|a|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$|b|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

for each test case, print a single integer, the minimum number of replacement operations needed.

If it's impossible, print -1.

Example
Input
3
turtle purtel
2
1 6
4 5
abc def
0
hello world
1
1 2
Output
3
3
4