Faktor ağacları

Фaktor ağacı, hər bir zirvəsi p olan, yarpaq olmayan, iki uşağı q və r olan ikili ağacdır. Bu ağacda p = q ∗ r və r ≠ 1, q ≠ 1 şərtləri ödənilir. Sadə ədədlər ağacın yarpaqlarıdır.

Aşağıda 24 üçün faktor ağacları göstərilmişdir:

Bu, 24 üçün mümkün olan dörd faktor ağacıdır.

Fredo, [l, r] intervalında kökü olan və zirvə kimi x olan neçə faktor ağacının mövcud olduğunu öyrənmək istəyir, çünki o, təcrübələr etməyi sevir.

İki faktor ağacı fərqli sayılır, əgər onlar izomorf deyilsə.

İki ağac izomorf adlanır, əgər biri digərindən, hər hansı bir zirvələr dəstində sağ və sol alt ağacların dəyişdirilməsi ilə əmələ gələ bilərsə. Uşaqlar hər hansı bir səviyyədə zirvələrdə dəyişdirilə bilər. İki boş ağac izomorfdur.

Bu iki ağac izomorfdur.

Yuxarıda göstərilən dörd faktor ağacı 24 üçün fərqlidir, çünki onlar verilmiş tərifə uyğundur.

Fərqli faktor ağaclarının sayını hesablamaq üçün bir proqram yazın.

Giriş məlumatları

Birinci sətir testlərin sayını t ( 1 ≤ t ≤ 10^5) ehtiva edir. Növbəti t sətirin hər biri x (2 ≤ x ≤ 500), l, r (2 ≤ l ≤ r ≤ 5000) üç tam ədədini ehtiva edir, şərtdə göstərildiyi kimi.

Çıxış məlumatları

Hər sorğu üçün fərqli faktor ağaclarının sayını ayrı sətirdə çıxarın.