Açarların saxlanması
Карл açarların saxlanması üçün bir xidmət hazırlayır. Hər bir istifadəçinin müsbət tam ədədi açarı var.
Karl bilir ki, açarları adi mətn şəklində saxlamaq yaxşı təcrübə deyil. Buna görə də, açarı saxlamaq əvəzinə, açarın izini saxlamağa qərar verdi. Lakin mövcud barmaq izi alqoritmlərindən birini istifadə etmək ona çox darıxdırıcı gəldi, buna görə də öz alqoritmini icad etdi.
Karlın izi aşağıdakı proseslə hesablanır: verilmiş tam ədədi 2-yə bölün, sonra nəticəni 3-ə bölün, sonra nəticəni 4-ə bölün və s., nəticə sıfıra bərabər olana qədər (hər dəfə tam bölmədən danışırıq). Barmaq izi bu bölmələrin qalıqlarının çoxluq dəsti kimi müəyyən edilir.
Məsələn, Karlın barmaq izi alqoritmi 11 açarına belə tətbiq olunur: 11-i 2-yə böləndə qalıq 1 və nəticə 5 olur, sonra 5-i 3-ə böləndə qalıq 2 və nəticə 1 olur, və 1-i 4-ə böləndə qalıq 1 və nəticə 0 olur. Beləliklə, 11 açarı [1, 2, 1] qalıqlar ardıcıllığını yaradır və barmaq izi çoxluq dəsti {1, 1, 2} olur.
Ksenya Karlın barmaq izi alqoritminin çox da yaxşı olmadığını sübut etmək istəyir. Məsələn, o aşkar etdi ki, həm 178800, həm də 123456 açarları {0, 0, 0, 0, 2, 3, 3, 4} barmaq izini yaradır. Beləliklə, istifadəçilər 123456 kimi tez-tez istifadə olunan və asanlıqla təxmin edilə bilən açarlarla barmaq izi toqquşması riski ilə üzləşirlər.
Ksenya sözlərinin daha inandırıcı olmasını istəyir. O, bəzi tez-tez istifadə olunan açarların siyahısında olan açarlarla eyni barmaq izinə malik digər açarların sayını hesablamaq istəyir. Sizin vəzifəniz ona kömək etməkdir.
Giriş məlumatları
Birinci sətir t tam ədədini (1 ≤ t ≤ 50000) - yoxlanılacaq tez-tez istifadə olunan açarların sayını ehtiva edir. Növbəti t sətirin hər biri bir tam ədəd k[i] (1 ≤ k[i] ≤ 10^18) - açarın özünü ehtiva edir.
Çıxış məlumatları
Hər bir açar üçün bir tam ədəd çıxarın - eyni barmaq izinə malik digər açarların sayı.
İzah
11 ilə eyni barmaq izinə malik digər açar 15-dir. 15 [1, 1, 2] qalıqlar ardıcıllığını yaradır. Beləliklə, hər iki ədəd {1, 1, 2} barmaq izi çoxluq dəstinə malikdir.