#include <bits/stdc++.h>
#define spd ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
using ll = long long;

#define N 1000005
#define MAX 1e18

vector<ll> powers;
set<ll> squares;
set<ll> s;

void powersPrecomputation()
{
    for (ll i = 2; i < N; i++) {
        squares.insert(i * i);
        if (squares.find(i) != squares.end()) continue;
        ll temp = i;
        while (i * i <= MAX / temp) {
            temp *= (i * i);
            s.insert(temp);
        }
    }
    for (auto x : s) powers.push_back(x);
}

ll calculateAnswer(ll L, ll R)
{
    ll perfectSquares = floor(sqrtl(R)) - floor(sqrtl(L - 1));
    ll high = (upper_bound(powers.begin(), powers.end(), R) - powers.begin());
    ll low = (lower_bound(powers.begin(), powers.end(), L) - powers.begin());
    perfectSquares += (high - low);
    return perfectSquares;
}

int main()
{
    powersPrecomputation();
    ll L = 1;
    ll R; cin >> R;
    cout << R - calculateAnswer(L, R) + 1 << endl;
    return 0;
}
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define RREP_(i, a_, b_, a, b, ...) for (Int i = Int(b) - 1, low##i = (a); i >= low##i; i--)
#define RREP(i, ...) RREP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on
struct in {
    template <class T> operator T() {
        T t;
        std::cin >> t;
        return t;
    }
};
void out() { std::cout << "\n"; }
template <class Head, class... Tail> void out(Head&& h, Tail&&... t) {
    std::cout << h << (sizeof...(Tail) == 0 ? "" : " "), out(std::forward<Tail>(t)...);
}
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }
template <class T> using V = std::vector<T>;

/**
 *    author:  knshnb
 *    created: Sun Feb 28 00:29:14 JST 2021
 **/

V<V<Int>> solve(Int n) {
    V<V<Int>> ret(1);
    REP(i, 1 << n) ret[0].push_back(i < (1 << (n - 1)));
    if (n == 1) return ret;
    auto sub = solve(n - 1);
    REP(t, 2) {
        for (auto& v : sub) {
            ret.push_back({});
            for (Int x : v) ret.back().push_back(x);
            for (Int x : v) ret.back().push_back(t ? !x : x);
        }
    }
    return ret;
}
signed main() {
    Int n = in();
    auto res = solve(n);
    out(res.size());
    for (auto& v : res) {
        for (Int x : v) std::cout << char('A' + x);
        out();
    }
}
