Most Difficult Problem Ever

You are given a function like below:

long long F(int A, int B, int C, long long x)  {
    long long res = A * x * x + B * x + C ;
    return res;
}

You are given five integers A, B, C, L, R.

You have to calculate the number of integer values of x such that x > 0 and L ≤ F(A, B, C, x) ≤ R.

Input

First line of input contains an integer T, number of test case.

For each test case there will be given five integers A, B, C, L, R.

Constraints:

1 ≤ T ≤ 1000000.

1 ≤ A, B, C ≤ 9.

1 ≤ L ≤ R ≤ 1000000000000000000.

Output

For each test case print the desired answer.

Sample

Input	Output
2 1 2 3 4 20 2 4 5 1 20	3 1

Note: Dataset is huge, use faster input, output.