Ninja’s Safe

After an accident, Ninja is suffering from transient amnesia. He wants to open his safe but has forgotten his password.

The safe’s lock has 4 circular wheels. Each wheel has 10 slots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The wheels can rotate clockwise as well as anti-clockwise: for example, we can turn 9 to be 0, or 0 to be 9. Each move consists of turning one wheel in one slot.

The lock initially starts at 0000, a string representing the state of the 4 wheels.

Ninja is given a list of ‘blockages’ dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning, and Ninja would be unable to open it.

There would be a ‘result’ given representing the wheels' value that will unlock the lock, return the minimum total number of turns Ninja is required to open the lock, or -1 if it is impossible for him to open it.

Help Ninja to open his safe.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘blockages’ array.

The next line contains ‘N’ space-separated strings denoting the values of the ‘blockages’ array.

The third line contains a single string denoting the ‘result’ value.

Output Format :

For each test case, print a single line containing numbers of turns or -1 as per the condition.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5 
1 <= N <= 500
blockages[i].length ==  4
result.length ==  4
result will not be in the list blockages
result and blockages[i] consists of only digits from ‘0’ to ‘9’.

Time Limit: 1sec