Write functions to implement a basic set of operations $($create$,$ delete, traverse, search $($key$)$

a linked list. Moreover add functions to do the following:

$($A$)$ Concatenate two given lists into one big list. $[5]$ node $*$concatenate $($node

$*$head$1,$ node $*$head$2)$;

Input:

$2468$

Output:

$1357246$

Input

$1357$

$246$

$12345678$

$($C$)$ Insert an element in

void insert$\_$sorted $($node $**$ head, node $*$element$)$ Input: $,391116$

Output: $391115$

$,16$

$($D$)$ Alwaysinsert elements at one end, and delete elements from the other end $($first$-$in first$-$out QUEUE$).[10]$

void insert$\_$q $($node $****$ head, node $*$element$)$

node Return the deleted node

Input $($for insertion$)$:

$3579$

Output:

$($E$)$ Always Insert elements at one end, and delete elements from the other end $($last$-$in first$-$out

void insert$\_$s $($node $****$ head, node $*$element$)$

node Return the deleted node $63579$

Input $($for deletion$)$:

$3579$

Output:

Input $($for insertion$)$:

$3579$

$6$

Output:

$63579$

Input $($for deletion$)$:

$3579$

Output:

$($F$)$ Return the second$-$highest element in the list $($unsorted input$)[10]$ node

$*$second$\_$highest$($node $**$ head$)$

Input

Output $47$

This is new year and there is a special game being played at IITJ. $[50]$ These are the

ways how the game is played.

There are say $\text{'}x\text{'}$ students in the class. Each student is labeled from $1($firststudent$)$ to $x$

$($last student$).$

A paper is given to $n-$th student.

The next $p-$th student who gets the paper quits the game.

The paper is passed until there is one last stude game. $5.$ The student becomes the class leader.

Now, your task is to find the number of such students.

Input

The first line contains a number $T(0T106)$

Each of the next $T$ lines contains $3$ integers which are $xx(0$

$x)$ and are separated $by$ a single space.

Output

For each test case, print the required answer.

Examples:

Input:

$412523$

Output: