An integer array is a good array if we can make the whole array empty by applying the following operation an arbitrary number of times:
For given and you have to tell the number of good arrays of length whose elements are between and , inclusive.
First line contains one integer — the number of test cases.
Each of the following lines contains two integers and .
For each test case output the answer modulo .
Input | Output |
---|---|
1 4 2 | 6 |
The following arrays are good for and : . No other arrays for and are good. |