Abel qrupları
Berlandiya ölkəsində, N şəhərində belə bir ənənə var. Əgər bir qız gənc bir oğlanla evlənmək istəyirsə və oğlanın ona altı muncuqdan ibarət bütün mümkün boyunbağıları hədiyyə etmək planı yoxdursa, qız hər gün ona N nizamlı yeni bir abel qrupu hədiyyə etməlidir. Yalnız bütün mümkün abel qrupları hədiyyə edildikdən sonra, oğlan hər gün ona altı muncuqdan ibarət yeni bir boyunbağı hədiyyə etməyə razı olacaq və nəhayət, onlar evlənəcəklər. Əgər iki abel qrupu izomorfikdirsə, onlar eyni sayılır və yalnız birini hədiyyə etmək lazımdır. Afina adlı bir qız çox məşğul bir proqramçı olan Petya adlı bir oğlana aşiq oldu. İndi o, oğlanın ona boyunbağı hədiyyə etməyə razı olana qədər neçə gün abel qruplarını hədiyyə etməli olduğunu bilmək istəyir.
Abel qrupları ilə bağlı əsas anlayışları və faktları xatırladaq.
Abel qrupu G=(A,*) cütüdür, burada A müəyyən bir çoxluqdur və * A üzərində ikili əməliyyatdır, yəni A çoxluğundan olan istənilən iki element a və b üçün a*b elementi də A-ya aiddir. Bu zaman abel qrupunun aksiomları adlanan aşağıdakı xassələr yerinə yetirilməlidir:
(i) Assosiativlik: istənilən a, b, c A üçün (a*b)*c=a*(b*c) bərabərliyi yerinə yetirilir.
(ii) Elə bir e A mövcuddur ki, istənilən a A üçün a*e=e*a=a bərabərlikləri yerinə yetirilir.
(iii) İstənilən a A üçün elə bir b A mövcuddur ki, a*b=b*a=e bərabərlikləri yerinə yetirilir.
(iv) Kommutativlik: istənilən a, b A üçün a*b=b*a bərabərliyi yerinə yetirilir.
Abel qrupunun mühüm bir nümunəsi n nizamlı tsiklik qrupdur: 0 ilə n-1 arasındakı ədədlər çoxluğu və n modulunda toplama əməliyyatı. Bu, Z_n kimi göstərilir.
İki abel qrupunun G=(A,*) və H=(B,·) birbaşa cəmi GH =(C,×) cütüdür, C={(a,b) : aA, bB} və (a_1, b_1)×(a_2, b_2) = (a_1 * a_2, b_1 · b_2) bütün a_1, a_2 A və b_1, b_2 B üçün.
İki qrup G=(A,*) və H=(B,·) izomorfik adlanır, əgər A-dan B-yə qarşılıqlı təkabül edən f təsviri mövcuddur ki, f(a_1)·f(a_2)=f(a_1*a_2) bütün a_1, a_2 A üçün.
Abel qruplarının nəzəriyyəsinin fundamental teoremi deyir ki, istənilən sonlu abel qrupu bəzi tsiklik qrupların birbaşa cəminə izomorfikdir.
Qalıqlar haqqında Çin teoremi deyir ki, Z_mn yalnız və yalnız m və n qarşılıqlı sadə olduqda Z_mZ_n-yə izomorfikdir.
Son iki ifadə n nizamlı bütün abel qruplarını izomorfizmə qədər təsvir etməyə imkan verir.
Məsələn, əgər n sadədirsə, o zaman n nizamlı bütün qruplar Z_n-yə izomorfikdir.
4 nizamlı 2 qeyri-izomorfik qrup mövcuddur: Z_4 və Z_2Z_2.
27 nizamlı 3 qeyri-izomorfik qrup mövcuddur: Z_27, Z_9Z_3 və Z_3Z_3Z_3.
36 nizamlı 4 qeyri-izomorfik qrup mövcuddur: Z_4Z_9, Z_2Z_2Z_9, Z_4Z_3Z_3 və Z_2Z_2Z_3Z_3.
Giriş verilənləri
Giriş faylının ilk sətirində T ≤ 500 təbii ədədi verilir, testlərin sayı. Sonrakı T sətirlərinin hər birində N ≤ 10^18 təbii ədədi verilir.
Çıxış verilənləri
Giriş faylındakı hər bir N ədədi üçün ayrıca sətirdə izomorfizmə qədər N nizamlı abel qruplarının sayını çıxarın.