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

Date: 2009-05-05
Time limit: 10s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

Strange thing happening ! If

yellow_agony @ 9 Jan 2010 07:41 PM

Strange thing happening ! If i submit one of  solutions from main contest written in JAVA , it gets Ac  , but if i write same in c++ evn with some optimisations , i get tle !

i m not getting ...... the

AnoopNarang @ 27 May 2010 02:12 AM

i m not getting ...... the time limit of problem is 10s ... but all successful submissions have taken time more than 15s ??

I have already said you

triplem @ 27 May 2010 03:08 AM

I have already said you should read the FAQ. Please do so.

can anyone explain me the

sachdeva @ 21 Dec 2010 04:00 PM

can anyone explain me the output of any test case??

i m not getting it...

Did you see how big a and b

triplem @ 16 Jan 2011 11:55 AM

Did you see how big a and b could be? A 10 million times 10 million loop is of course not going to work within the time limit. You need a much better algorithm.

my program is running

maxstell @ 31 Jan 2012 10:08 AM
my program is running successfully in my desktop but giving 'Time limit exceeded' while running in your enviroment.pls help.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions