LCA in a Binary Search Tree

You are given a binary search tree (BST) containing N nodes. Additionally, you have references to two nodes, P and Q, within this BST.

Your task is to determine the Lowest Common Ancestor (LCA) of these two nodes. The LCA of two nodes P and Q is defined as the lowest node in the BST that has both P and Q as descendants (allowing a node to be a descendant of itself).

Input:

The first line contains an integer 'T', representing the number of test cases.

For each test case: 
 - The first line contains two space-separated integers P and Q, indicating the nodes whose LCA needs to be found.
 - The second line contains integers representing the BST elements in level order, separated by spaces. If a node does not have a left or right child, it is represented by -1.

Output:

For each test case, print the LCA of nodes P and Q on a separate line.

Example:

Example input for a tree:

1
2 3
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation of the example:

• Level 1: Root node is 1.
• Level 2: Left child of 1 is 2 and right child is 3.
• Level 3: Left child of 2 is 4 (right is -1/null), left of 3 is 5, right is 6.
• Level 4: Right child of 4 is 7; others are null (-1).
• The input ends when all nodes at the final level are null (-1).

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 5000
• 0 ≤ Data ≤ 10⁶ and Data ≠ -1

Note:

The format explained was to clarify how input is generated for a given tree structure. All elements for the tree levels are space-separated in one line.