1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
#include <stack>
#include <unordered_set>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define MP make_pair
#define FOR(v,p,k) for(int v=(p);v<=(k);++v)
#define FORD(v,p,k) for(int v=(p);v>=(k);--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

#define ODD(x) ((x)%2)
#define EVEN(x) (!(ODD(x)))

class Primes {
public:
    VI primes;
    VI tmp;
    int max_n;
    VI is_prime;
    Primes(int max_n) : max_n(max_n), is_prime(max_n+1, 1) {
        is_prime[0]=is_prime[1]=0;
        int p=2;
        int j=p*p;
        while (j<=max_n) {
            int k=j;
            while (k<=max_n) {
                is_prime[k]=0;
                k+=p;
            }
            p+=1;
            while (!is_prime[p]) {
                p+=1;
            }
            j=p*p;
        }
        REP(i, max_n+1) {
            if (is_prime[i]) {
                primes.PB(i);
            }
        }
    }

    void fill_prime_divisors(int n, VI &divisors) {
        int max_prime = (int) floor(sqrt(n));
        assert(max_prime <= max_n);
        FOREACH(i, primes) {
            if (*i > max_prime) break;
            while ((n % *i) == 0) {
                divisors.PB(*i);
                n /= *i;
            }
        }
    }

    void fill_small_prime_and_all_divisors(int n, VI &prime_divisors, unordered_set<int> &divisors) {
        fill_prime_divisors(n, prime_divisors);
        divisors.insert(1);
        FOREACH(i, prime_divisors) {
            tmp.clear();
            FOREACH(d, divisors) {
                tmp.PB((*d)* (*i));
            }
            std::copy(tmp.begin(),tmp.end(),std::inserter(divisors, divisors.end()));
        }
        tmp.clear();
        FOREACH(i, divisors) {
            tmp.PB(n/(*i));
        }
        std::copy(tmp.begin(),tmp.end(),std::inserter(divisors, divisors.end()));
    }

};

int main() {
    int n;
    scanf("%d", &n);
    LL res = 0LL;
    Primes primes((int) floor(sqrt(n)));

    VI prime_divisors, prime_divisors2;
    unordered_set<int> divisors, divisors2;
    primes.fill_small_prime_and_all_divisors(n, prime_divisors, divisors);

    FOREACH(a, divisors) {
        int na = n/(*a) -1;
        if (na < 6 ) continue;
        prime_divisors2.clear();
        divisors2.clear();
        primes.fill_small_prime_and_all_divisors(na, prime_divisors2, divisors2);

        FOREACH(bb, divisors2) {
            int cc = na/(*bb) - 1;
            if ((*bb > 1) && (cc > 1)) ++res;
        }
    }


    printf("%lld\n", res);
    return 0;
}