Факторні дерева
Факторним деревом називається бінарне дерево, в якому кожна вершина 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) згідно з умовою.
Вихідні дані
Виведіть кількість різних факторних дерев для кожного запиту в окремому рядку.