A linked list contains N nodes numbered from 1 to N. The tail of the list points to head of the list i.e. the linked list is circular in nature.

For when N=5

1->2->3->4,

^-------5<---'

An integer K is also given to you.You start counting from head and when you reach Kth node in the circular list you remove that node. For eg. if K=7 we start from head i.e. 1 right now nd move K steps ahead till we reach node numbered 3 in circular list 1->2->3->4->5->1->2->[3] <---- we remove this node

now the new linked list looks like this

1->2->4,

^---5<---'

Node numbered 3 has been removed and now we start counting from the next node. This process is repeated until only one Node is left.

Your task is to determine the number of the last node.

INPUT FORMAT:

Line 1: Number of test cases T Line 2: 2 Integers N K , N=Number of nodes in circular list and K=Number of steps to count

CONSTRAINTS: 1<=T<=10 1<=N<=1000 1<=K<=10^8

OUTPUT FORMAT:

T lines,containing Number of the last node remaining for each case

NOTE: This question must be solved using linked list.