Факторные деревья
Факторным называется бинарное дерево, в котором каждая вершина p, не являющаяся листом, имеет двух детей q и r, такие что p = q ∗ r и r ≠ 1, q ≠ 1. Простые числа являются листами дерева.
Следующие деревья являются факторными для 24:
Это четыре всевозможных факторных дерева для 24.
Так как Фредо любит делать эксперименты, он хочет знать сколько существует факторных деревьев с корнем в интервале [l, r] и которые содержат x как вершину.
Два факторные дерева считаются разными, если они не изоморфны.
Два дерева называются изоморфными, если одно из них может быть образовано из другого серией преобразований, состоящих в обмене правого и левого поддерева у любого набора вершин. Детей можно обменивать у вершин на любом уровне. Два пустые дерева изоморфны.
Эти два дерева изоморфны.
Приведенные выше четыре факторные дерева для числа 24 различны, так как они удовлетворяют приведенному определению.
Напишите программу, которая посчитает количество различных факторных деревьев.
Входные данные
Первая строка содержит количество тестов t ( 1 ≤ t ≤ 10^5). Каждая из следующих t строк содержит три целые числа x (2 ≤ x ≤ 500), l, r (2 ≤ l ≤ r ≤ 5000) как указано в условии.
Выходные данные
Вывести количество различных факторных деревьев для каждого запроса в отдельной строке.