Гарри узнал от Дамблдора, что медальон Салазара Слизерина является крестражем. Этот медальон раньше находился в доме 12 на площади Гриммо, доме матери Сириуса Блэка. Он был украден оттуда и теперь находится в Министерстве Магии в офисе Долорес Амбридж, бывшей преподавателя Защиты от Темных искусств.
Гарри, Рон и Гермиона проникли в Министерство. Когда они добрались в офис Амбридж, они увидели кодовый замок, который требует их сосчитать количество магических чисел от l до r включительно.
Гарри помнит со времен занятий у Амбридж, что она определяет магическое число как число, которое, будучи переведенным в систему счисления с основанием b, имело четное число каждой из цифр от 0 до b - 1 в записи без ведущих нулей.
Вам нужно ответить на q запросов замка. Каждый запрос задается тремя целыми числами bi, li и ri — основание и отрезок, для которых вам нужно посчитать количество магических чисел.
Примечание
В примере 1 для первого запроса переведя числа от 4 до 9 в систему счисления по основанию 2, мы получим:
- 4 = 1002,
- 5 = 1012,
- 6 = 1102,
- 7 = 1112,
- 8 = 10002,
- 9 = 10012.
Среди них только 9 в системе счисления по основанию 2 имеет четное число 1 и 0. Поэтому ответ равен 1.