#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>


using namespace std;

#define int long long
vector<pair<int,int>> pq;   // в этом списке будут хранится пары p * q
vector<pair<pair<int,int>,int > > pqr;  // в этом списке будут хранится тройки p*q *r

vector<int> primes; // список простых чисел


const int border = 10000; // граница до которой хотим генерить числа


const int maxpow = 5;


bool is_prime(int n)    // функция для проверки числа на простоту
{
    for (int i = 2; i*i<=n; i++)    // если число делится на какое нибудь число до корня то оно составное
        if (n%i==0)
            return false;
    return true;    // если не делится то оно простое
}
void gen_prime() // функция которая находит простые числа
{

    for (int i = 2; i<border; i++)
       if(is_prime(i))  // если число простое добавляем его в список
        primes.push_back(i);
}

bool cmp(pair<int,int> a, pair<int,int> b)  // компоратор для сортировки двоек
{
    return a.first*a.second<b.first*b.second;
}
bool cmp2(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) //компоратор для сортировки троек
{
    return a.first.first*a.first.second*a.second<b.first.first*b.first.second*b.second;
}
void gen_pq()    // генерируем двойки до нужной границы(до 100)
{
    for (int i = 1; i<primes.size(); i++)   // пробегаем по всем простым и пытаемся сгенерить двойки
        for (int j = i; j<primes.size(); j++)
        {
            int p = primes[i];
            int q = primes[j];

            if (p*q>=border)  // если двойка больше границы то дальше нет смысла смотреть и происходит выход из цикла
                break;
            else    // иначе добавляем в список двоек
                pq.push_back({primes[i],primes[j]});
        }
    sort(pq.begin(),pq.end(),cmp);  // сортим двойки
}

void gen_pqr()
{
    for (int i = 1; i<primes.size(); i++)
        for (int j = i; j<primes.size(); j++)
        {
            int p = primes[i];
            int q  = primes[j];
            int r = primes[j];
            if (p*q*r>=border)  // если тройка больше границы то дальше нет смысла смотреть и происходит выход из цикла
                break;
            for (int k = j; k<primes.size(); k++)
            {

                r = primes[k];
                if (p*q*r>=border)// если тройка больше границы то дальше нет смысла смотреть и происходит выход из цикла
                    break;
                else // иначе добавляем тройку в список троек
                    pqr.push_back({{primes[i],primes[j]},primes[k]});
            }
        }
    sort(pqr.begin(),pqr.end(),cmp2);   // сортим тройки
}

int phi (int n) {   // стандартный алгоритм для вычисления функции Эйлера

    int result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

vector<int> get_divisors(int n) // функция которая возвращает список делителей числа n
{
    vector<int> res;
    for (int i = 1; i*i<=n; i++)
    {
        if (n%i==0) // смотрим если n делится на i
        {
            res.push_back(i);   // то добавляем i в список

            if (n/i!=i) //здесь мы добавляем вторую пару но смотрим если n/i не равно i то n/i Тоже добавляем в список
                res.push_back(n/i); //зачем это делать? например рассмотрим число 16.
                                    // 16 делится на 1 и 16/1!=1
                                    // добавляем 1 и 16
                                    // потом добавляем 2 и 8
                                    // при i = 4 16 делится на 4 поэтому добавим 4 в список
                                    // теперь смотрим 16/i = 16/4 = 4. так как 16/i ==i не добавляем в список а то получится что 4 добавится 2 раза
                                    // то есть для 1 пара 16, для 2 пара 8, для 4 пара 4.
                                    // в итоге в список добавится 1 2 4 8 16, причем 4 только 1 раз
        }
    }
    sort(res.begin(),res.end());    // сортим делители
    return res;
}


vector<int> intersect(vector<int> a, vector<int> b) // стандартный алгоритм для пересечения двух отсортированных списков, который возвращает отсортированное пересечение
{
    int i = 0, j = 0;
    vector<int> res;
    while (i<a.size() && j<b.size())
    {
        if (a[i]<b[j])
            i++;
        else
            if (a[i]>b[j])
                j++;
            else
            {
                res.push_back(a[i]);
                i++;
                j++;
            }
    }
    return res;
}


vector<vector<int>> getclasses(vector<int> D)   // функция для разбиения множетсва на классы bin()
{   // например если в множестве числа {1,2,3,4}
    //индекс массив означает на какую максимальную степень двойки делится число
    // в bin[0] добавится 1 3, то есть 1 и 3 делятся на 2^0 и не делятся на 2^1
    // в bin[1] добавится 2. сюда не добавляем 4 так как 2^1 не максимальная степень на которую делится 4
    // в bin[2] добавится 4.
    vector<char>used(D.size());
    vector<vector<int>>bin(maxpow);
    for (int b = maxpow-1; b>=0; b--)
    {
        for (int i = 0; i<D.size(); i++)
        {
            if (used[i])
                continue;
            if ((D[i] & ( (1ll<<b)-1))==0)      // это проверка на делимость
            {
                bin[b].push_back(D[i]);
                used[i] = 1;
            }
        }
    }

    return bin;

}

int calcpq(int p, int q)// функция для подсчета числа свидетелей для чисел вида n = p*q. тут все делаю как написано в методичке
{

    vector<int> divP = get_divisors(p-1);

    vector<int> divQ = get_divisors(q-1);

    vector<int> D = intersect(divP, divQ);



    int s[maxpow];
    vector<vector<int>> bin = getclasses(D);
    int ans = 0;
    for (int i = 0; i<maxpow; i++)
    {
        s[i] = 0;
        for (int j = 0;j<bin[i].size(); j++)
            s[i]+=phi(bin[i][j]);

        ans+=s[i]*s[i];
    }
    return ans;
}
int calcpqr(int p, int q, int r)    // функция для подсчета числа свидетелей для чисел вида n = p*q*r. делаю все так как написано в методичке
{
    int n = p*q*r;
    vector<int> divP = get_divisors(p-1);
    vector<int> divQ = get_divisors(q-1);
    vector<int> divR = get_divisors(r-1);

    divP = intersect(divP, get_divisors(n/p-1));
    divQ = intersect(divQ, get_divisors(n/q-1));
    divR = intersect(divR, get_divisors(n/r-1));

    vector<vector<int>> bin1 = getclasses(divP);
    vector<vector<int>> bin2 = getclasses(divQ);
    vector<vector<int>> bin3 = getclasses(divR);
    int ans = 0;

    for (int i = 0; i<maxpow; i++)
    {
        int s1 = 0,s2 = 0, s3 = 0;

        for (int j = 0; j<bin1[i].size(); j++)
            s1+=phi(bin1[i][j]);

        for (int j = 0; j<bin2[i].size(); j++)
            s2+=phi(bin2[i][j]);

        for (int j = 0; j<bin3[i].size(); j++)
            s3+=phi(bin3[i][j]);

        ans+=s1*s2*s3;
    }
    return ans;
}

signed main()
{

    double starttime = clock();// засекаем время начала работы программы
    ofstream cout("output.txt");

    gen_prime();
    gen_pq();
    gen_pqr();


    for (auto it:pq)    // считаем соотношение для двоек
    {
        if (it.second!=it.first)
        {
            int x = calcpq(it.first,it.second);
            cout << it.first*it.second << " " ;
            cout <<fixed << setprecision(20) << x*1.0 / phi(it.first*it.second) << endl;
        }
    }


    cout << endl;
    for (auto it:pqr)   // тут считаем для троек
    {
        int x = calcpqr(it.first.first,it.first.second,it.second);
        cout << it.first.first *it.first.second *it.second << " ";

        cout <<fixed << setprecision(20) << x*1.0 / phi(it.first.first*it.second*it.first.second) << endl;

    }
    // что значат числа в файле? пусть x - количество свидетелей простоты
    // Рабин доказал то что x<=phi(n)/4, где phi(n) - функция Эйлера
    // то есть x/phi(n)<=1/4. 1/4 это грубая оценка, которая редко достигается, в файл выводятся реальные оценки то есть x/phi(n)

    double endtime = clock();   // засекаем когда программа завершила работу
    cerr << (endtime-starttime)/CLOCKS_PER_SEC << endl; // считаем сколько секунд отработала программа
}