Detect Cycle in a Linked List

You are given a singly linked list containing n nodes, where each node contains an integer value. In addition, you are provided with an integer pos that represents the zero-indexed position at which the tail of the linked list is connected to form a cycle. If pos is -1, then there is no cycle in the linked list.

Your task is to detect if a cycle exists in the linked list, and if so, return the value of the node where the cycle begins. If no cycle exists, output 0.

Note: Use the Floyd’s Tortoise and Hare algorithm for cycle detection. The cycle detection algorithm works in two phases. In the first phase, two pointers slow and fast traverse the list and if they meet, a cycle is detected. In the second phase, reset one pointer to the head and move both pointers at the same pace; their meeting point is the start of the cycle.

Formally, if the linked list is represented as

$$l_0 \rightarrow l_1 \rightarrow \cdots \rightarrow l_{n-1}, $$

and if there exists an index pos such that l_{n-1}.next = l_{pos}, then the cycle begins at node l_{pos}.

inputFormat

The input is read from stdin and is structured as follows:

1. An integer T representing the number of test cases.
2. For each test case:
   1. An integer n representing the number of nodes in the linked list.
   2. A line with n space-separated integers denoting the node values. (If n = 0, this line will be empty.)
   3. An integer pos denoting the position (0-indexed) where the tail connects to form a cycle. If pos = -1, no cycle exists.

outputFormat

For each test case, print a single line to stdout containing the value of the node where the cycle begins. If no cycle exists, print 0.

## sample

3
4
3 2 0 -4
1
2
1 2
0
1
1
-1

2
1
0

</p>