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 .
1 4 2
The following arrays are good for and : .
No other arrays for and are good.