Algorithm

A. Immobile Knight
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a chess board of size n×m�×�. The rows are numbered from 11 to n, the columns are numbered from 11 to m.

Let's call a cell isolated if a knight placed in that cell can't move to any other cell on the board. Recall that a chess knight moves two cells in one direction and one cell in a perpendicular direction:

Find any isolated cell on the board. If there are no such cells, print any cell on the board.

Input

The first line contains a single integer t (1t641≤�≤64) — the number of testcases.

The only line of each testcase contains two integers n and m (1n,m81≤�,�≤8) — the number of rows and columns of the board.

Output

For each testcase, print two integers — the row and the column of any isolated cell on the board. If there are no such cells, print any cell on the board.

Example
input
Copy
3
1 7
8 8
3 3
output
Copy
1 7
7 2
2 2

Note

In the first testcase, all cells are isolated. A knight can't move from any cell of the board to any other one. Thus, any cell on board is a correct answer.

In the second testcase, there are no isolated cells. On a normal chess board, a knight has at least two moves from any cell. Thus, again, any cell is a correct answer.

In the third testcase, only the middle cell of the board is isolated. The knight can move freely around the border of the board, but can't escape the middle.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
int check = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j >= m; j++){
if((i + 2 <= n && j+1 <= m)||(i + 2 <= n && j-1 >= 1)||(i-2 >= 1 && j +1 <= m)||(i-2 >= 1 && j -1 >= 1)
||(j+2 <= m && i+1 <= n) || (j+2 <= m && i-1 >= 1) ||(j-2 >= 1 && i +1 <= n)||(j-2 >= 1 && i -1 >= 1)){
continue;
}
else{
cout<<i<<" "<<j<<endl;
check = 1;
}
if(check){
break;
}
}
if(check){
break;
}
}
if(!check){
cout<<1<<" "<<1<<endl;
}
}

}
Copy The Code &

Input

cmd
3
1 7
8 8
3 3

Output

cmd
1 7
7 2
2 2