N kids in a kindergarten sit in a circle waiting for their teacher to share candies. M (M>=N) candies are to be shared, and it is not sure that all the kids can get the same number of candies. To ensure the distribution will be as fair as possible, the teacher decides that the difference of numbers of candies any two neighboring kids get should not be greater than 1, and that each kid gets at least one candy. How many different methods can you employ to share candies?

The first line in the input is an integer K (1<=K<=50) representing the number of test cases. The following K lines are K test cases. Each line contains two integers N and M (2<=N<=M<=50) separated by one space, where the first integer N representing the number of kids and the second integer M representing the number of candies.

提交代码