E. Безумная задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны пять целых чисел $$$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$$$.
Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит пять целых чисел $$$k$$$, $$$l_1$$$, $$$r_1$$$, $$$l_2$$$ и $$$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$$$).

Выходные данные

Для каждого набора входных данных выведите количество подходящих упорядоченных пар $$$(x, y)$$$ на новой строке.

Пример
Входные данные
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
Примечание

В третьем наборе входных данных подходящие упорядоченные пары следующие:

  • $$$(5,15)$$$
  • $$$(5,45)$$$
  • $$$(6,18)$$$
  • $$$(6,54)$$$
  • $$$(7,21)$$$
  • $$$(7,63)$$$

В четвертом наборе входных данных единственная допустимая упорядоченная пара это $$$(1,1\,000\,000\,000)$$$