Prime Factor

All submissions for this problem are available.
You start with a sequence of consecutive integers. You want to group them into sets.
You are given the interval, and an integer P. Initially, each number in the interval is in its own set.
Then you consider each pair of integers in the interval. If the two integers share a prime factor which is at least P, then you merge the two sets to which the two integers belong.
How many different sets there will be at the end of this process?
Input
One line containing an integer C, the number of test cases in the input file.
For each test case, there will be one line containing three singlespaceseparated integers A, B, and P. A and B are the first and last integers in the interval, and P is the number as described above.
Output
For each test case, output one line containing the number of sets..
Example
Input: 2 10 20 5 10 20 3 Output: 9 7
Author:  codecheftsec 
Tags  codecheftsec 
Date Added:  18022013 
Time Limit:  0.833333 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 