Даны пять целых чисел \(k\), \(l_1\), \(r_1\), \(l_2\) и \(r_2\). Вам нужно помочь Wave посчитать количество упорядоченных пар \((x, y)\), таких что выполняются все следующие условия:
- \(l_1 \leq x \leq r_1\).
- \(l_2 \leq y \leq r_2\).
- Существует неотрицательное целое число \(n\), такое что \(\frac{y}{x} = k^n\).
Выходные данные
Для каждого набора входных данных выведите количество подходящих упорядоченных пар \((x, y)\) на новой строке.
Примечание
В третьем наборе входных данных подходящие упорядоченные пары следующие:
- \((5,15)\)
- \((5,45)\)
- \((6,18)\)
- \((6,54)\)
- \((7,21)\)
- \((7,63)\)
В четвертом наборе входных данных единственная допустимая упорядоченная пара это \((1,1\,000\,000\,000)\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861
|
12
1999999987
6
1
197
|