eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Факторные деревья

Факторные деревья

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

Факторным называется бинарное дерево, в котором каждая вершина p, не являющаяся листом, имеет двух детей q и r, такие что p = qr и r1, q1. Простые числа являются листами дерева.

Следующие деревья являются факторными для 24:

prb4040.gif

Это четыре всевозможных факторных дерева для 24.

Так как Фредо любит делать эксперименты, он хочет знать сколько существует факторных деревьев с корнем в интервале [l, r] и которые содержат x как вершину.

Два факторные дерева считаются разными, если они не изоморфны.

Два дерева называются изоморфными, если одно из них может быть образовано из другого серией преобразований, состоящих в обмене правого и левого поддерева у любого набора вершин. Детей можно обменивать у вершин на любом уровне. Два пустые дерева изоморфны.

prb4040_1.gif

Эти два дерева изоморфны.

Приведенные выше четыре факторные дерева для числа 24 различны, так как они удовлетворяют приведенному определению.

Напишите программу, которая посчитает количество различных факторных деревьев.

Вхідні дані

Первая строка содержит количество тестов t ( 1t10^5). Каждая из следующих t строк содержит три целые числа x (2x500), l, r (2lr5000) как указано в условии.

Вихідні дані

Вывести количество различных факторных деревьев для каждого запроса в отдельной строке.

Приклад

Вхідні дані #1
2
6 2 24
16 192 192
Вихідні дані #1
5
18