PLATON - Platon and Socrates

no tags 

Platon and Socrates one day decided to play a new game. They asked their friend to think of two numbers between 1 and 5000, not equal. Then they asked him to tell the product to Platon and the sum to Socrates. After that they tried to figure out what these numbers are. They played a lot of times but none of them could guess these numbers. Finally they made it!! Here is the dialogue:

  • [P] : I don't know the answer.
  • [S] : I knew you wouldn't know, I don't know it either.
  • [P] : Now I know it.
  • [S] : I know it too.
Your task is to find all pairs Platon and Socrates could have been thinking about. Numbers are limited to the given range.

Input

Input starts with a single integer t, the number of test cases (t<=2000). t test cases follow. Each test case consists of one line containing two integers l r separated by a single space, denoting the range of numbers ( 1<= l < r <=5000, r-l < 200 ).

Output

For the i-th test case output a line with the text case i. In the next line print n - number of pairs from range (l, r). Then exactly n lines follow with two numbers separated by single space. The first number is not greater than the second. Pairs are printed in increasing sum order.

Example

Input:
2
1 10
2 8

Output:
case 1
0
case 2
0

hide comments
:D: 2019-11-29 13:33:27

The description is unfortunately unclear in key parts. To summarize: both Plato and Socrates know the range (l, r) (as stated by XilinX below) and they will use that knowledge in their analysis. (1, 5000) range in first paragraph is misleading, because that will never be an actual (l, r) range in data set. The range (l, r) is open, so numbers x, y to be guessed meet the conditions: l < x < y < r. That means that some (l, r) ranges could have no valid x, y query pairs. I don't know if x can be equal to y. It makes a difference for the results (see problem RECTANGLE). I tested both versions and they both pass, so test cases are weak.

Sushovan Sen: 2017-07-06 09:47:47

why 2,9 cannot be a solution for first test case.

Walrus: 2012-09-05 12:49:27

What range does "between 1 and 5000" refer to ? [1,5000), or (1,5000], or (1,5000) or [1,5000] ?

tld: 2010-06-08 13:21:33

Admin,coule you give out an example?
L ,R , a pair of answer?

Last edit: 2010-06-08 13:22:02
Jonathan Schmidt-Dominé: 2010-05-11 14:32:37

Why is 1,6 not a solution when l = 1 and r = 10?

[Trichromatic] XilinX: 2009-04-15 05:55:43

0.00 running time in the ranklist is a very useful hint.

Lox: 2009-04-15 04:32:04

Any non-trivial cases?

[Trichromatic] XilinX: 2009-02-17 01:18:47

Both Plato & Socrates know the range (l,r).

Paul Draper: 2009-02-16 20:06:31

Are l and r limits on OUR output or one the numbers Plato and Socrates consider?


Added by:Bogusław K. Osuch
Date:2005-04-14
Time limit:15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Resource::P