John Snow recently discovered his blood relationship with Daenerys Targaryen, so he wanted to meet her and tell the entire truth. John has already heard about the dragons of Daenerys, so he decided to take gifts for the dragons.

He knew dragons love to eat chocolates, Yes, Dragons too love the chocolates :) . However, they get furious if they see less than 'm' chocolates at a time.

John brought ‘n’ number of chocolates and infinite number of boxes from the market. John asked his intelligent friend Samwell Tarly to put chocolates in the boxes in such a way that opening a gift box will not make the dragon furious.

Samwell is ready to do the task, but wonders in how many ways he can put the chocolates into the boxes such that dragons don't become furious after opening the box. Since, Samwell Tarly is in hurry, as he has to shoot for the next episode, can you quickly tell him the number of ways he can put the chocolates inside the boxes.

See sample test explanation for more details.

Input : First line contains an integer ‘T’, i.e. the number of test cases.

Each test case has two spaced integers ‘n’ and ‘m’, i.e. the total no. of chocolates and the minimum no. of chocolates to be put in each box repectively.

Output : A single new line containing the number of ways in which Samwell Tarly can put the chocolates inside the boxes.

Constraints :

1<=T<=250
1<=n,m<=250