Вы играете в игру на сетке $$$n \times m$$$, в которой компьютер загадал некоторую клетку $$$(x, y)$$$ сетки, а вы должны определить, какую именно.
Для этого вы выберете какое-то $$$k$$$ и какие-то $$$k$$$ клеток $$$(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$$$, и дадите их компьютеру. В ответ вы получите $$$k$$$ чисел $$$b_1,\, b_2, \ldots b_k$$$, где $$$b_i$$$ — манхэттенское расстояние от $$$(x_i, y_i)$$$ до скрытой клетки $$$(x, y)$$$ (то есть вы знаете, какое расстояние соответствует какой из $$$k$$$ клеток).
Получив эти $$$b_1,\, b_2, \ldots, b_k$$$, вы должны суметь определить загаданную клетку. Для какого наименьшего $$$k$$$ всегда можно правильно угадать загаданную клетку, независимо от того, какую клетку выберет компьютер?
Напомним, что манхэттенское расстояние между клетками $$$(a_1, b_1)$$$ и $$$(a_2, b_2)$$$ равно $$$|a_1-a_2|+|b_1-b_2|$$$.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — количество строк и количество столбцов в сетке.
Для каждого набора входных данных выведите одно целое число — минимальное значение $$$k$$$ для этого набора входных данных.
2 2 3 3 1
2 1
В первом наборе входных данных наименьшее такое $$$k$$$ равно $$$2$$$, для него можно выбрать, например, клетки $$$(1, 1)$$$ и $$$(2, 1)$$$.
Обратите внимание, что для $$$k = 2$$$ нельзя выбрать клетки $$$(1, 1)$$$ и $$$(2, 3)$$$, так как обе клетки $$$(1, 2)$$$ и $$$(2, 1)$$$ дадут $$$b_1 = 1, b_2 = 2$$$, поэтому мы не сможем определить, какая клетка скрыта, если компьютер выберет одну из них.
Во втором наборе входных данных следует выбрать $$$k = 1$$$, для него можно выбрать клетку $$$(3, 1)$$$ или $$$(1, 1)$$$.
| Codeforces Global Round 17 |
|---|
| Закончено |
