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

Гарри узнал от Дамблдора, что медальон Салазара Слизерина является крестражем. Этот медальон раньше находился в доме 12 на площади Гриммо, доме матери Сириуса Блэка. Он был украден оттуда и теперь находится в Министерстве Магии в офисе Долорес Амбридж, бывшей преподавателя Защиты от Темных искусств.

Гарри, Рон и Гермиона проникли в Министерство. Когда они добрались в офис Амбридж, они увидели кодовый замок, который требует их сосчитать количество магических чисел от l до r включительно.

Гарри помнит со времен занятий у Амбридж, что она определяет магическое число как число, которое, будучи переведенным в систему счисления с основанием b, имело четное число каждой из цифр от 0 до b - 1 в записи без ведущих нулей.

Вам нужно ответить на q запросов замка. Каждый запрос задается тремя целыми числами bi, li и ri — основание и отрезок, для которых вам нужно посчитать количество магических чисел.

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

Первая строка содержит одно целое число q (1 ≤ q ≤ 105) — число запросов.

Каждая из следующих q строк содержит три целых числа bi, li, ri (2 ≤ bi ≤ 10, 1 ≤ li ≤ ri ≤ 1018).

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

Выведите q строк, на каждой выведите одно целое число — ответ на очередной запрос.

Примеры
Входные данные
2
2 4 9
3 1 10
Выходные данные
1
2
Входные данные
2
2 1 100
5 1 100
Выходные данные
21
4
Примечание

В примере 1 для первого запроса переведя числа от 4 до 9 в систему счисления по основанию 2, мы получим:

  • 4 = 1002,
  • 5 = 1012,
  • 6 = 1102,
  • 7 = 1112,
  • 8 = 10002,
  • 9 = 10012.

Среди них только 9 в системе счисления по основанию 2 имеет четное число 1 и 0. Поэтому ответ равен 1.