Beauty Factor

Mehedi and Burhan are two friends. Yesterday they have participated in a class of sorting. Actually they have recently learned sorting numbers. Today was the second class of sorting. Professor invented a new type of sorting numbers. He gave this task to Mehedi and Burhan as homework.

Professor defines the beauty of a number n as count of distinct prime factor of n. So, beauty of 1, 2, 3, 4, 5, 6 are 0, 1, 1, 1, 1, 2 respectively because 1 has no prime factor and 4 has only one distinct prime factor.

He sorts numbers according to beauty. Number having smaller beauty will come first than having larger beauty. If two numbers have the same beauty, then a smaller number comes first. So if he sorts first 10 natural numbers then the order will be - 1, 2, 3, 4, 5, 7, 8, 9, 6, 10. So, summation of the numbers from index 7 to 9 is 8 + 9 + 6 = 23

Mehedi and Burhan tried to solve this problem, but they were not able to solve all the cases as it seemed complex to them. Can you help them by doing the same for T test cases?

Input

First line will have T, number of test cases.
Each test case will have 4 integers - N, X, L, R.
You have to create an array of length N with first N natural numbers starting from X.
So, A = [ X, X+1, X+2,…,X+N-1]. Sort them according to the above method.
Now after sorting, calculate sum of the numbers from index L to R that is A[L] + A[L+1]+…+A[R-1]+A[R].

1 <= T <= 2*105

1 <= N <= 105

1 <= X <= 105

1 <= L <= R <= N

X + N - 1 <= 105

Output

For each test case print the sum between L and R.

Sample

5
6 1 5 6
10 1 5 6
10 1 1 1
10 2 7 8
10 3 5 10

11
12
1
20
56