You are given two words - beginWord and endWord. You also have a wordList of size n.
All words are of the same length.

You have to create a transformation sequence from beginWord to endWord that looks like this:
beginWord → str1 → str2 → str3 → ... → strk

Adjacent pairs in the sequence differ by a single character, and all strings from str1 to strk lie in wordList.
Also strk = endWord.

Find the minimum number of words in the shortest possible transformation sequence. If such a sequence is not possible return 0.

Example:

beginWord = "work"
endWord = "tech"
wordList = ["toch","worh","wock","woch","tech","werh"]
Output: 5
Explanation: Shortest transformation sequence is "work" → "wock" → "woch" → "toch" → tech", which is 5 words long.

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has three lines:

• Two space-separated strings beginWord and endWord.
• An integer n denoting the number of words in the wordList.
• n space-separated strings denoting the word list.

Output Format

For each test case, the output has a line containing the shortest possible transformation sequence.

Sample Input

2
work tech
6
toch worh wock woch tech werh
black white
7
aracz blacz bracz ahacz white ahace ahice

Expected Output

5
0

1 <= T <= 10
1 <= n <= 5000
1 <= string length <= 5