K-th Smallest Element in a BST

Given a Binary Search Tree (BST), your task is to find the k-th smallest element in the tree. A BST is defined as follows: for any node with value v, all elements in its left subtree are less than v and all elements in its right subtree are greater than v.

In mathematical notation, if \(\text{inorder}(\text{BST}) = [a_1, a_2, \dots, a_n]\) represents the sorted order of elements obtained by an inorder traversal, then you need to output \(a_k\) (1-indexed).

You are given multiple test cases. For each test case, you will be provided with a list of integers to build the BST and a number k. Your program should construct the BST by inserting the integers in the given order and then output the k-th smallest element.

inputFormat

The first line of input contains a single integer (T), the number of test cases. Each test case consists of two lines:

1. The first line contains space-separated integers representing the elements to be inserted into the BST.
2. The second line contains a single integer (k), which specifies the k-th smallest element to find in the BST.

Note: Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the k-th smallest element in the BST. Output is written to standard output (stdout).## sample

1
5 3 8 1 4
3

4