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