Условие

---

I. ПОРЯДЪК
---
Мими обича теорията на числата. Това е една от топ 10 на любимите ѝ дисциплини в математиката. Вчера, четейки предпочитания от нея учебник, отново срещна едно от любимите си понятия – мултипликативен порядък на число по модул n (или просто порядък). Тя е възхитена от грациозността на това понятие и, след като ви припомни дефиницията му, иска да решите една задачка, свързана с него. И така: ако са дадени две взаимно прости числа (a, n) = 1, то показател на a по модул n наричаме най-малкото положително цяло число b, за което е изпълнено ab ≡ 1 (mod n). Т.е. остатъкът на ab при деление на n е 1. Забележете, че това понятие е добре дефинирано – ако две числа a и n са взаимно прости, тогава винаги има поне едно b, за което ab ≡ 1 (mod n). Например, според теоремата на Ойлер, a^Fi(n) ≡ 1 (mod n), където Fi(n) е функцията на Ойлер за даденото число n – броят на естествените положителни числа по-малки от n и взаимно прости с него. За удобство ще считаме, че ако две числа a и n  не са взаимно прости, то порядъкът на a по модул n също е дефиниран и е 0. Мими иска от вас да напишете програма, която по зададено число a, намира порядъците на a по модул всички числа в даден интервал.

Вход: 
Програмата трябва да може да обработва няколко примера при едно изпълнение. На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери. Всеки тест се състои от един ред, на който ще са зададени три цели числа A, F и T – числото, чиито порядъци търсим, началото и края на интервала, от който се интересуваме, съответно. 

Изход: 
За всеки пример програмата трябва да изведе на отделен ред на стандартния изход сумата на порядъците на А по модул всички числа в затворения интервал [F, T].

Ограничения: 
1 ≤ A ≤ 10^6, 1 ≤ F ≤ 10^6, 1 ≤ T ≤ 10^6, F ≤ T, T – F ≤ 10^5.

Примерен вход:
2
7 8 11
123012 3 100001	

Примерен изход:
19
610202925