Maximum Reachable Tree Height

You are given several test cases. In each test case, there are N trees positioned on a 2D grid. Each tree is given by its coordinates and height as a triple \((x_i, y_i, h_i)\). A bird starts at one of these trees and can only move to an adjacent tree if the following condition holds:

\((x_1 = x_2 \text{ and } |y_1 - y_2| = 1) \quad \text{or} \quad (y_1 = y_2 \text{ and } |x_1 - x_2| = 1)\)

Additionally, the bird can only move from a tree to a neighboring tree if the neighbor tree's height is greater than or equal to the height of the current tree. Your task is to compute the maximum height the bird can reach starting from a specified tree in each test case.

The input begins with an integer T representing the number of test cases. For each test case, the first number is an integer N, followed by N lines, each containing three integers xi, yi, and hi. The test case concludes with an integer S indicating the starting tree index (1-indexed).

inputFormat

The first line contains an integer T representing the number of test cases. For each test case:

• The first line contains an integer N (the number of trees).
• Then follow N lines, each with three integers xi, yi, and hi separated by spaces.
• The next line contains an integer S (the 1-indexed starting tree).

outputFormat

For each test case, output a single line containing the maximum height the bird can reach from the starting tree.

## sample

2
4
0 0 10
0 1 20
1 0 15
1 1 25
1
3
3 3 5
4 3 6
5 3 2
2

25
6

</p>