Primes in the GCD table

Problem code: D4

All submissions for this problem are available.

Johnny has created a table which encodes the results of some operation -- a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height a and width b), indexed from (1,1) to (a,b), and with the value of field (i,j) equal to gcd(i,j). He wants to know how many times he has used prime numbers when writing the table.

Input

First, t ≤ 10, the number of test cases. Each test case consists of two integers, 1 ≤ a,b < 107.

Output

For each test case write one number - the number of prime numbers Johnny wrote in that test case.

Example

Input:
2
10 10
100 100

Output:
30
2791

Author: admin
Date Added: 5-05-2009
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

balakrishnan_v @ 3 Jun 2009 12:58 PM

I dont believe my solution exceeds the time limit. It runs in under 2 seconds on my computer. And how come the submitted solution has a time of 27.05 seconds?

team12 @ 3 Jun 2009 04:23 PM

The time limit is 10s,isn't it????????

abhijith @ 3 Jun 2009 05:37 PM

if there are more the one input files the time taken for each file is added to the total

abhijith @ 3 Jun 2009 05:42 PM

10 s is time limit for one input file

anshuman_singh @ 3 Jun 2009 08:25 PM

@balakrishnan the reason for that might be that the server machine may be slower than your system... so the run time may not match your system's run time.

balakrishnan_v @ 4 Jun 2009 02:16 PM

ok, here is what I dont understand. I modified the program to output values for a=b=10^7 and the code ran in less than 8 seconds and gave wrong answer(obviously). According to the problem statement, the code should take in values less than 10^7 and hence any input must terminate in less than 8 seconds.
How is this possible?

fr0d @ 4 Jun 2009 04:06 PM

@balakrishnan note that the number of test cases can be 10...will all the 10 test cases finish within 10 sec?

keshav_57 @ 5 Jun 2009 02:50 PM

What is the memory limit for the problem?

kyun @ 6 Jun 2009 12:30 AM

Is there a constraint on b-a (lesser than 10^7-1) assuming a<=b?

gerrob @ 8 Jun 2009 11:44 PM

The problemsetter has got really small experience about rejudge. My knowledge shows from other judges that rejudging slows down the judge. And after the rejudge by resubmitting of a previous AC code that is TLE after rejudge can be again AC. As you can see: my code id=36404 was TLE after rejudge, but I've resubmitted and it is AC again (code id=36498).

Just a note: before rejudge there were 5 AC, after rejudge only 2.

You can play by rejudge, if you are lucky then all codes will get TLE. But I think it isn't worth.

srinivas @ 10 Jun 2009 12:47 AM

My code got TLE for test case number 4, but how can the memory be 0k?

u2001137 @ 11 Jun 2009 06:42 AM

Is there any issue with testing system? My code is running for a file with 300 test cases in less than 10 seconds - and I have tested it well for most diverse input. How can the same code give TLE for just max 10 cases here?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions