Insert Interval Problem Statement

You are provided with a list of 'N' non-overlapping intervals, each defined by two integers, 'start' and 'end', sorted in ascending order by 'start' values. Your task is to insert a given interval into the list so that all intervals remain in sorted order.

If the given interval overlaps with any existing intervals, you must merge all necessary intervals to maintain a list of only non-overlapping intervals.

Input:

The first line of input contains an integer ‘T’, the number of test cases.
The first line of each test case contains a positive integer ‘N’, the number of intervals in the list.
Subsequent ‘N’ lines contain two space-separated integers ‘start’ and ‘end’, representing existing intervals.
The following line contains two space-separated integers, ‘start’ and ‘end’ for the interval to be inserted.

Output:

For each test case, return the list of intervals after inserting the given interval.

Example:

Suppose the list of intervals is: [[1,3], [5,7], [8,12]] and you need to insert the interval [4,6].
Insert [4,6] in the list which results in merging [4,6] with [5,7] to form [4,7].
The final list is: [[1,3], [4,7], [8,12]]

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 10⁴
• 1 ≤ start ≤ end ≤ 10⁵

Note:
You do not need to print anything; simply implement the function as specified.