You have been given a linked list where each node has a single character. You have also been given a string 'STR'.

You have to remove all the occurrences of string STR from the linked list.

Note:

1. Start checking from the end of the linked list and not from the beginning. For example, if the linked list is ( a, b, a ,b, a)  and the string is equal to “aba” , then the answer should be (a b), not (b a).

2. After removing an occurrence check again for new formations.

Input format:

The first line contains an Integer 'T' which denotes the number of test cases.

The first line of each test case contains the elements of the singly linked list which are the characters not separated by a space.

The second line of each test case contains the string named 'STR'.

Output format:

For each test case, return the head of the linked list with updated character nodes after removing occurrences of the string.

Note:

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

Constraints:

1 <= T <= 10
0 <= N <= 10^3  
0 <= K <= 10^2

Where 'N' is the size of the singly linked list and 'K' is the size of the string.

Time limit: 1 sec