Word Distance

You are given a document as an Array/List 'ARR' of words of length ‘N’. You have to perform Q queries. In each query, you are given two words. Your task is to find the smallest distance between these two words in a document and return it.

Distance between words is defined as the difference between their indexes.

For example:

ARR=[‘hot’, ‘a’, ‘b’, ‘dog’] and query = (‘hot’, ‘dog’) 

The answer, in this case, is 3 as the minimum distance between ‘hot’ and ‘dog’ in the given document is 3.  

Note:

If any one of the words is not present in the document then your program must return ‘N’ which is the length of the document.

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated integers, ‘N’ and ‘Q’ respectively.

The second line of each test case contains all the space-separated words in the document ARR.

The next ‘Q’ lines of each test case contain ‘Q’ queries, as two, space-separated words. 

Output Format:

For each test case print ‘Q’ lines, i’th of which is the answer to i’th query.

Answer to each query is printed on a new line. 

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^4
1 <= Q <=100

Where, ‘N’ and ‘Q’, are the length of the ARR, number of queries, respectively. 

All the strings in ARR contain only lowercase English letters. 

Time Limit: 1 sec