Modular Node

You are given a singly linked list containing ‘N’ nodes, where every node in the linked list contains a pointer “next” which points to the next node in the list and having integer values. You are also given an integer ‘K’.

You recently studied modular operation and you wanted to find out the last node in the linked list such that ‘x%K’ = 0 , where ‘x’ is the position of the node from the beginning.

Return the last node that satisfies the above property.

Example :

N = 7 , K = 3
Linked List = 1 -> 3 -> 2 -> 4 -> 6 -> 5 -> 7

Explanation : 

The first node has ‘x%K’ = 1%3 = 1.
The second node has ‘x%K’ = 2%3 = 2.
The third node has ‘x%K’ = 3%3 = 0.
The fourth node has ‘x%K’ = 4%3 = 1.
The fifth node has ‘x%K’ = 5%3 = 2.
The sixth node has ‘x%K’ = 6%3 = 0.
The seventh node has ‘x%K’ = 7%3 = 1.
So, the last node which has ‘x%k’ = 0 is the sixth node with value 5.

Input Format :

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

The first line of each test case contains two space-separated integers ‘N’ denoting the number of nodes in the linked list and ‘K’.

The next line of the test case contains ‘N + 1’ space-separated integers which are the nodes of the linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.

Output format :

For each test case, output an integer denoting the value of the last node with ‘x%K’ = 0. 

Print the output of each test case in 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^5
1 <= K <= N
Sum of N over all Test cases <= 10^5

Time Limit : 1 sec