e-olymp
Соревнования

Dynamic programming on Trees - Top Level

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

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

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

prb4040.gif

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

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

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

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

prb4040_1.gif

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

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

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

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

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

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

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

Лимит времени 1 секунды
Лимит использования памяти 122.17 MiB
Входные данные #1
2
6 2 24
16 192 192
Выходные данные #1
5
18