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

on 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:

$($B$)$ Concatenate two given list into a concatenated list such that the final list is in sorted order

$[7]$

Input

$1357$

Output:

$12345678$

$($C$)$ Insert an element in a element to be inserted. $[8]$

void insert$\_$sorted $($node ${?}^{****}$ head, node $*$element$)$; Input: $,391116$

$15$

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$)$

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 student who hasn't left the 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 $x(0$

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

output

For each test case, print the required answer

Examples:

Input:

$2412523$

Output: $21$