TAP2013H  Horace and his primes
[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013problems.pdf]
Horace likes to play writing natural numbers in the blackboard in his bedroom. One of his favourite games consists in first writing a number n, then the sum of all the different prime numbers that divide n, and so on until the number written on the board becomes a prime number. For example, if Horace begins writing the number n = 90, because 90 = 2 × 3^{2} × 5 the next number to be written will be 2 + 3 + 5 = 10; then, as 10 = 2 × 5 Horace will write the number 2 + 5 = 7; finally, because 7 is a prime number the game will end here.
Formally, in this game each natural number n ≥ 2 defines a sequence whose first element is n, and each new element is the sum of all the prime numbers that divide the previous element in the sequence. The order of the game is the position of the first prime number in the sequence, and coincides with the total amount of numbers written on the blackboard once the game has ended. In the example from the previous paragraph, with n = 90 the order of the game is K = 3, because the numbers that are written will be 90, 10 and 7.
Now, not all games are equally entertaining to Horace, and in this case he prefers to begin by writing a number n such that the order of the corresponding game is a particular value K. Horace would like to know how many different values of n between A and B inclusive satisfy this condition, but because he does not know how to code he needs someone to do this calculation for him. Can you help him?
Input
The first line contains an integer P which indicates the number of questions Horace wants to ask you (1 ≤ P ≤ 10^{5}). Each of the next P lines describes a question using three integer numbers A, B and K, which mean that Horace would like to know how many different values of n satisfy that A ≤ n ≤ B and the order of the game beginning with n is K (2 ≤ A ≤ B ≤ 10^{6} and 1 ≤ K ≤ 10^{6}).
Output
You should print P lines, each one containing an integer number with the answer to one of the questions made by Horace, in the order in which they appear in the input.
Example 1
Input: 1 90 90 3 Output: 1
Example 2
Input: 5 2 9 1 2 9 2 800 810 4 999999 1000000 2 100000 1000000 1000000 Output: 4 4 5 2 0
hide comments
viratian_070:
20170707 13:36:32
precomputation helps 

Govind Lahoti:
20151214 18:20:06
nice problem :) 

kp:
20150705 08:07:04
awesome problem, try NFACTOR after this Last edit: 20150705 08:18:57 

Rishabh:
20141008 09:40:27
Getting TLE any suggestions??


Rishav Goyal:
20140929 17:03:05
cubic cluster rocks ;) 

Alok Sharma:
20140929 17:03:05
@all: awesom problem,brings up my 100 

Ouditchya Sinha:
20140929 17:03:05
@Fidel Schaposnik : Very nice problem, loved solving it. Thank You! :) 

nitish rao:
20140929 17:03:05
@all.. try this one also ODDDIV :) 
Added by:  Fidel Schaposnik 
Date:  20131007 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2013 