Algorithm

A. Anti Light's Cell Guessing
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1610/A
input
standard input
output
standard output

You are playing a game on a n×m�×� grid, in which the computer has selected some cell (x,y)(�,�) of the grid, and you have to determine which one.

To do so, you will choose some k� and some k� cells (x1,y1),(x2,y2),…,(xk,yk)(�1,�1),(�2,�2),…,(��,��), and give them to the computer. In response, you will get k� numbers b1,b2,…bk�1,�2,…��, where bi�� is the manhattan distance from (xi,yi)(��,��) to the hidden cell (x,y)(�,�) (so you know which distance corresponds to which of k� input cells).

After receiving these b1,b2,…,bk�1,�2,…,��, you have to be able to determine the hidden cell. What is the smallest k� for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?

As a reminder, the manhattan distance between cells (a1,b1)(�1,�1) and (a2,b2)(�2,�2) is equal to |a1−a2|+|b1−b2||�1−�2|+|�1−�2|.

Input

The first line of the input contains a single integer t� (1≤t≤1041≤�≤104) — the number of test cases. The description of test cases follows.

The single line of each test case contains two integers n� and m� (1≤n,m≤1091≤�,�≤109) — the number of rows and the number of columns in the grid.

Output

For each test case print a single integer — the minimum k� for that test case.

Example
input
Copy
2
2 3
3 1
output
Copy
2
1
Note

In the first test case, the smallest such k� is 22, for which you can choose, for example, cells (1,1)(1,1) and (2,1)(2,1).

Note that you can't choose cells (1,1)(1,1) and (2,3)(2,3) for k=2�=2, as both cells (1,2)(1,2) and (2,1)(2,1) would give b1=1,b2=2�1=1,�2=2, so we wouldn't be able to determine which cell is hidden if computer selects one of those.

In the second test case, you should choose k=1�=1, for it you can choose cell (3,1)(3,1) or (1,1)(1,1).

 

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;
    if(n == 1 && m == 1){
      cout<<0<<endl;
      continue;
    }
    else if( n == 1 || m == 1){
      cout<<1<<endl;
      continue;
    }
    else{
      cout<<2<<endl;
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
2 3
3 1

Output

x
–
+
cmd
2
1
Advertisements

Demonstration

Codeforcess Solution 1610-A A. Anti Light's Cell Guessing ,C++, Java, Js and Python ,1610-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+