Факторіал, степені та абелеві групи
Позначимо через f(n) число абелевих груп порядку n з точністю до ізоморфізму. Нехайь m та N - фіксовані натуральні числа. Потрібно для декількох пар натуральних чисел L та R таких, що L ≤ R ≤ N, знайти значення суми
Нагадаємо основні поняття та факти стосовно абелевих груп.
Абелева група це пара G=(A,*), де A - це деяка множина, а * - це бінарна операція на A, тобто довільним двом елементам a та b з A ставиться у відповідність елемент a*b, який також належитьA. При цьому повинні бути виконані наступні умови, які називають аксіомами абелевої групи:
(i) Асоціативність: для довільних a, b, c A виконується рівність (a*b)*c=a*(b*c).
(ii) Існує e A такий, що для довільного a A виконуються рівності a*e=e*a=a.
(iii) Для довільного a A існує b A такий, що виконуються рівності a*b=b*a=e.
(iv) Комутативність: для довільних a, b A викоеується рівність a*b=b*a.
Важливим прикладом абелевої групи є циклічна група порядку n: множина чисел від 0 до n-1 з операцією додавання по модулю n. Вона позначається як _n.
Прямою сумою двох абелевих груп G=(A,*) та H=(B,·) називається пара G H = (C, ×), где C={(a,b) : a A, b B} і (a_1, b_1) × (a_2, b_2) = (a_1 * a_2, b_1 · b_2) для усіх a_1, a_2 A і b_1, b_2 B.
Дві групи G=(A,*) та H=(B,·) називаються ізоморфними, якщо існує взаємно однозначне відображення f з A на B таке, що f(a_1)· f(a_2)=f(a_1 * a_2) для усіх a_1, a_2 A.
Фундаментальна теорема теорії абелевих груп стверджує, що довільна скінчена абелева група ізоморфна прямій сумі деяких циклічних груп.
Китайська теорема про залишки стверджує, що _mn ізоморфно _m _n тоді і лише тоді, коли m та n взаємно прості.
Останні два твердження дозволяють описувати усі абелеві групи порядку n з точністю до ізоморфізму.
Наприклад, якщо n - просте, то усі групи порядку n ізоморфні _n.
Існує 2 неізоморфні групи порядку 4: _4 і _2 _2.
Існує 3 неізоморфні групи порядку 27: _27, _9 _3 і _3 _3 _3.
Існує 4 неізоморфні групи порядку 36: _4 _9, _2 _2 _9, _4 _3 _3 і _2 _2 _3 _3.
Вхідні дані
У першому рядку вхідного файлу задано через пропуск натуральні числа m ≤ 10^9, N ≤ 200000 та T ≤ 10^5. У кожному з наступних T рядків задано через пропуск натуральні числа L, R ≤ N такі, щ L ≤ R.
Вихідні дані
Для кожної пары чисел L та R з вхідного файлу виведіть у окремому рядку значення відповідної суми.