Problem statement

There are rectangles with vertical and horizontal lengths of h and w, and square squares with a side length of 1 are spread inside. If the upper left cell is (0,0) and the cell to the right of j below (0,0) is represented as (i, j), (i, j) is i + j. If is even, it is painted red, and if it is odd, it is painted blue.

Now, the upper left vertex of (0,0) and the lower right vertex of (h − 1, w − 1) are connected by a line segment. If the length of the red part through which this line segment passes is a and the length of the blue part is b, the ratio a: b is an integer ratio. Express a: b in the simplest way (with relatively prime integers).

input


T
h_1 \ w_1
...
h_T \ w_T


One file contains T inputs. The T in the first line and the vertical and horizontal lengths h_i and w_i in the Tth input are input in the 1 + i line.

Constraint

* An integer
* 1 ≤ T ≤ 1000
* 1 ≤ h_i, w_i ≤ 109



output

Output the answer for each case separated by 1 and separated by spaces. It spans T lines in total.

sample

Sample input 1


3
twenty three
3 3
4 3


Sample output 1


1 1
Ten
1 1


<image>





Example

Input

3
2 3
3 3
4 3


Output

1 1
1 0
1 1
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    long long x,y;

	
    cin  >> x >> y;
    if(x==y)cout << 1 << " " << 0 << endl;
    else if(x%2==0||y%2==0)cout << 1 << " " << 1 << endl;
    else {
      if(x>y)swap(x,y);
      if(y%x==0){
	y/=x;
	x/=x;
      }
      while(1){
	int f=0;
	for(int j=2;j*j<y;j++){
	  if(x%j==0&&y%j==0){
	    f=1;
	    x/=j;
	    y/=j;
	  }
	}
	if(f==0)break;
      }
      // cout << x << y << endl;
      cout << x*y/2+1 << " " << x*y/2<< endl;
    }
  }
  return 0;
  
}