Problem - 3187

In mathematics, the greatest common divisor (gcd), of two non-zero integers, is the largest positive integer that divides both two numbers without a remainder. For example, gcd( 10, 15 ) = 5, gcd( 5, 4 ) = 1. If gcd( k, n ) == 1 , then we say k is co-prime to n ( also , n is co-prime to k ), the totient function H(n) of a positive integer n is defined to be the number of positive integers not greater than n that are co-prime to n. In particular H(1) = 1 since 1 is co-prime to itself (1 being the only natural number with this property). For example, H (9) = 6 since the six numbers 1, 2, 4, 5, 7 and 8 are co-prime to 9. Also, we define the number of different prime of n is P (n). For example, P (4) = 1 (4 = 2*2), P (10) = 2(10 = 2*5), P (60) = 3(2*2*3*5). Now, your task is, give you a positive integer n not greater than 2^31-1, please calculate the number of k (0 < k < 2^31) satisfied that H (k) = n and P (k) <= 3(So we called HP Problem).