E. Insane Problem
binary search; greedy; implementation; math; number theory
Wave is given five integers \(k\), \(l_1\), \(r_1\), \(l_2\), and \(r_2\). Wave wants you to help her count the number of ordered pairs \((x, y)\) such that all of the following are satisfied: \(l_1 \leq x \leq r_1\). \(l_2 \leq y \leq r_2\). There exists a non-negative integer \(n\) such that \(\frac{y}{x} = k^n\).
The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases.The only line of each test case contains five integers \(k\), \(l_1\), \(r_1\), \(l_2\), and \(r_2\) (\(2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9\)).
For each test case, output the number of matching ordered pairs \((x, y)\) on a new line.
In the third test case, the matching ordered pairs are the following: \((5,15)\) \((5,45)\) \((6,18)\) \((6,54)\) \((7,21)\) \((7,63)\) In the fourth test case, the only valid ordered pair is \((1,1\,000\,000\,000)\)