#include <bits/stdc++.h>
 
using namespace std;
 
// Function to compute the Euler's totient function for each number up to n
void computeTotient(int n, vector<int>& phi) {
    for (int i = 1; i <= n; i++) {
        phi[i] = i;
    }
 
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // Check if i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}
 
// Function to find and display numbers that are relatively prime to each number up to n
void displayRelativelyPrimeNumbers(int n, const vector<int>& phi) {
    for (int i = 1; i <= n; i++) {
        cout << "phi(" << i << ") = " << phi[i] << ": Relatively prime numbers are: ";
        for (int j = 1; j < i; j++) {
            if (__gcd(i, j) == 1) {
                cout << j << " ";
            }
        }
        cout << endl;
    }
}
 
int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
 
    vector<int> phi(n + 1);
    computeTotient(n, phi);
 
    displayRelativelyPrimeNumbers(n, phi);
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gY29tcHV0ZSB0aGUgRXVsZXIncyB0b3RpZW50IGZ1bmN0aW9uIGZvciBlYWNoIG51bWJlciB1cCB0byBuCnZvaWQgY29tcHV0ZVRvdGllbnQoaW50IG4sIHZlY3RvcjxpbnQ+JiBwaGkpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgIHBoaVtpXSA9IGk7CiAgICB9CiAgICAKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IG47IGkrKykgewogICAgICAgIGlmIChwaGlbaV0gPT0gaSkgeyAvLyBDaGVjayBpZiBpIGlzIHByaW1lCiAgICAgICAgICAgIGZvciAoaW50IGogPSBpOyBqIDw9IG47IGogKz0gaSkgewogICAgICAgICAgICAgICAgcGhpW2pdID0gcGhpW2pdIC8gaSAqIChpIC0gMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCi8vIEZ1bmN0aW9uIHRvIGZpbmQgYW5kIGRpc3BsYXkgbnVtYmVycyB0aGF0IGFyZSByZWxhdGl2ZWx5IHByaW1lIHRvIGVhY2ggbnVtYmVyIHVwIHRvIG4Kdm9pZCBkaXNwbGF5UmVsYXRpdmVseVByaW1lTnVtYmVycyhpbnQgbiwgY29uc3QgdmVjdG9yPGludD4mIHBoaSkgewogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgY291dCA8PCAicGhpKCIgPDwgaSA8PCAiKSA9ICIgPDwgcGhpW2ldIDw8ICI6IFJlbGF0aXZlbHkgcHJpbWUgbnVtYmVycyBhcmU6ICI7CiAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPCBpOyBqKyspIHsKICAgICAgICAgICAgaWYgKF9fZ2NkKGksIGopID09IDEpIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgaiA8PCAiICI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGludCBuOwogICAgY291dCA8PCAiRW50ZXIgdGhlIHZhbHVlIG9mIG46ICI7CiAgICBjaW4gPj4gbjsKCiAgICB2ZWN0b3I8aW50PiBwaGkobiArIDEpOwogICAgY29tcHV0ZVRvdGllbnQobiwgcGhpKTsKCiAgICBkaXNwbGF5UmVsYXRpdmVseVByaW1lTnVtYmVycyhuLCBwaGkpOwoKICAgIHJldHVybiAwOwp9

MTI=

12