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