Find the K-th Smallest Element in a Binary Search Tree

Given a binary search tree (BST) constructed by inserting nodes in a specific order, your task is to find the k-th smallest element in the BST. In a BST, for any given node, every element in its left subtree is less than the node's value, and every element in its right subtree is greater than or equal to the node's value.

The k-th smallest element is defined as the element that appears in the k-th position when the BST's elements are sorted in ascending order. This is typically achieved by performing an inorder traversal (i.e., traversing the left subtree, the root, and then the right subtree).

Your solution should build the BST from the given list of values (in the order they are provided) and then determine the k-th smallest element using an appropriate traversal method.

Note: Ensure that your solution reads input from standard input (stdin) and writes the output to standard output (stdout).

inputFormat

The input begins with an integer T denoting the number of test cases. Each test case consists of three lines:

• The first line contains an integer N, the number of nodes to insert into the BST.
• The second line contains N space-separated integers, representing the values inserted into the BST in the given order.
• The third line contains an integer k, specifying that you should output the k-th smallest element (1-indexed).

outputFormat

For each test case, print the k-th smallest element in the BST on a separate line.

## sample

3
7
20 8 22 4 12 10 14
3
5
15 10 20 8 12
4
1
1
1

10
15
1

</p>