Lowest Common Ancestor in a Binary Tree

Given a fixed binary tree with the following structure:

                 3
               /   \
              5     1
             / \   / \
            6   2 0   8
               / \
              7   4

You are required to answer several queries. Each query contains two integers representing values of two nodes present in the tree. Your task is to find the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor between two nodes p and q is defined as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

The mathematical definition can be expressed in LaTeX as:

$$LCA(p,q) = \text{the node } v \text{ such that } v \text{ is an ancestor of both } p \text{ and } q \text{ and has the greatest depth.} $$

Note: The tree is fixed and does not need to be read from the input. Your program should build the tree internally and then process the queries from standard input.

inputFormat

The first line contains an integer Q, representing the number of queries. Each of the following Q lines contains two space-separated integers representing the values of two nodes for which the lowest common ancestor is to be computed. It is guaranteed that both node values exist in the tree.

outputFormat

For each query, output a single line containing the value of the lowest common ancestor (LCA) of the two given nodes.## sample

5
5 1
5 4
7 8
6 0
7 2

3
5
3
3
2

</p>