Факторні дерева#4040
Факторним деревом називається бінарне дерево, в якому кожна вершина , що не є листком, має двох дітей і , таких що p = q \cdot r і r \neq 1, q \neq 1. Прості числа є листками дерева.
Ось приклади факторних дерев для числа :
Це всі чотири можливі факторні дерева для .
Фредо, який любить експериментувати, хоче дізнатися, скільки існує факторних дерев з коренем у діапазоні [, ], які містять як вершину.
Два факторні дерева вважаються різними, якщо вони не ізоморфні.
Два дерева називаються ізоморфними, якщо одне з них може бути отримане з іншого шляхом серії перетворень, що полягають в обміні правого і лівого піддерева у будь-якого набору вершин. Дітей можна обмінювати у вершин на будь-якому рівні. Два пусті дерева ізоморфні.
Ці два дерева ізоморфні.
Наведені вище чотири факторні дерева для числа є різними, оскільки вони відповідають наведеному визначенню.
Напишіть програму, яка підрахує кількість різних факторних дерев.
Перший рядок містить кількість тестів (1 \le t \le 10^5). Кожен з наступних рядків містить три цілі числа (2 \le x \le 500), , (2 \le l \le r \le 5000) згідно з умовою.
Виведіть кількість різних факторних дерев для кожного запиту в окремому рядку.
Приклад 1