素数对

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>(); // 素数表
        Set<Integer> set = new HashSet<>(); // 加快第三个数的查找
        for (int i = 1; i <= n; i++) {
            if (prime(i)) {
                list.add(i);
                set.add(i);
            }
        }

        int m = list.size(), res = 0;
        for (int i = 0; i < m; i++) { // 取AC/BC减少选择范围:
            for (int j = i; j < m; j++) { // C>=A
                int a = list.get(i), c = list.get(j);
                int b = c * c - a;
                if (b > list.get(m - 1)) break; // C*C-A=B<=MAX

                if (set.contains(b)) {
                    if (a != b) res += 2; // AB、BA
                    else res++;
                }
            }
        }
        System.out.println(res);
    }

    // 判断素数
    private static boolean prime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}