IPAD - Ipad Testing

Apple recently released "the new Ipad" with several advance features. But the device was jailbroken within a week of its launch.  After learning the technique to jailbreak "the new Ipad", one of the enthusiast, Donncha O'Cearbhaill successfully installed different programming language compilers available from the cydia store on the device. Now O'Cearbhaill wants his friends to test these compilers. Being a good computer science student, he decided to use instead of traditional 'hello world' program, a new programming puzzle to test the compilers on the jailbroken devices :

For any α, β >= 0, how many positive integers are there which can't be expressed as αλ + βμ where gcd(λ,μ) = 1 and λ,μ > 1. Also find the maximum of all such possible integers. ( α, β, λ, μ are all integers )

O'Cearbhaill knew that neither the cydia store nor the app store has a decent text editor suitable for all programming languages, so he only accept programs less than equals to 100 characters in length.

Input

First line consist of T ( <= 1000 ). Next T lines has two integers λ and μ such that gcd(λ,μ) = 1 and  1 < λ, μ < 10^8.

Output

For each test case output the two required values separated by a single space in a single line.

Example

Input:
2
2 3
3 4

Output: 1 1
3 5

Added by:XeRoN!X
Date:2012-03-22
Time limit:1s
Source limit:100B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-03-10 00:32:14 Ritam Shukla
Whoa! The logic was insane! +1 for the problem setter. ;)

Last edit: 2013-03-14 13:24:52
2013-03-04 10:23:51 (Tjandra Satria Gunawan)(曾毅昆)
Too easy for python but nice problem for C :-)
2012-04-13 07:25:47 Devil D
Answer does not fit into 32 bit integer . Am i Correct ?
Re ( Author ) : Yes

Last edit: 2012-04-13 17:41:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.