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.

Discussion

Statistics


65% Solution Ratio

Riaz_BSMRSTUEarliest, 4M ago

sirpokaFastest, 0.1s

Riaz_BSMRSTULightest, 1.0 MB

Tariqul13579Shortest, 448B

Submit

Login to submit

Related Contests

BSMRSTU Intra University Programming Contest 2019 Ended at 2019-12-07 09:00:00 +0000 UTC
Replay of BSMRSTU Intra University Programming Contest 2019 Ended at 2019-12-09 18:00:00 +0000 UTC