Consider a set, , consisting of integers. The set is beautiful if at least one of the following conditions holds true for every :
For example, is beautiful but is not beautiful. Given two integers, and , can you find the number of different -element beautiful sets you can create using integers ?
Perform queries where each query consists of some and . For each query:
- Find the number of different beautiful sets having exactly elements that can be generated using integers in the inclusive range from to .
- Print the number of beautiful sets, modulo , on a new line.
Input Format
The first line contains an integer, , denoting the number of queries.
Each line of the subsequent lines consists of two space-separated positive integers describing the respective values of and for the query.
Constraints
Subtasks
- for of the maximum score.
Output Format
For each query, print the number of different beautiful sets of size that can be generated using integers in the inclusive range from to on a new line. As the answers to these queries can be quite large, each answer must be modulo .
Sample Input
2
6 4
27 2
Sample Output
6
26
Explanation
For the first query, the beautiful sets of size we can create using numbers from to are shown below:
As there are are six such sets, we print the result of on a new line.