Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Most Difficult Problem Ever

By RamprosadG · Limits 1s, 512 MB

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

InputOutput
2
1 2 3 4 20
2 4 5 1 20
3
1

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

69% Solution Ratio

Riaz_BSMRSTUEarliest, Dec '19

purpleFastest, 0.0s

Riaz_BSMRSTULightest, 1.0 MB

maraz_miaShortest, 288B

Submit

 BSMRSTU Intra University Programming Contest 2019 Dec '19 Replay of BSMRSTU Intra University Programming Contest 2019 Dec '19 