|
Time limit 1000/1000/1000/1000 ms. Memory limit 16000/16000/16000/16000 Kb.
Для проведения соревнования по спортивному программированию был оборудован прямоугольный зал. Рабочие машины были расставлены в N рядов по M штук в каждом ряду. Для удобства участников на некоторые компьютеры необходимо установить дополнительное программное обеспечение, чем и должен заняться начинающий системный администратор Вася. Каждый компьютер имеет уникальный номер от 1 до N×M . Зная этот номер, Вася может удалённо подключиться к этому компьютеру и установить на него необходимое ПО. Однако он не знает, в каком порядке компьютеры были пронумерованы. Исследовав оставшуюся после предыдущего сисадмина документацию, Вася обнаружил только небольшие заметки. В них говорилось, что нумерация компьютеров удовлетворяет следующим критериям: - Номер каждого компьютера строго меньше номеров компьютеров, находящихся непосредственно справа и снизу от него, если такие компьютеры существуют. - В одном из направлений (слева направо или сверху вниз, одинаковом для всех компьютеров) номер ближайшего компьютера больше ровно на 1. Олимпиада уже завтра, и поставить дополнительное ПО на компьютеры, на которых это не требуется, у Васи нет времени, а оставить участников без запрошенного дополнительного ПО запрещено регламентом той олимпиады. Поэтому Васе необходимо узнать количество компьютеров, чей номер не зависит от выбора нумерации компьютеров, удовлетворяющей описанным условиям. Формат входных данных В первой строке вводится количество тестовых случаев T (2 ≤ T ≤ 100). Далее следует описание тестовых случаев. В единственной строке каждого случая вводятся два целых числа Ni и Mi (1 ≤ Ni, Mi ≤ 1013) - стороны заполненного компьютерами прямоугольника. Формат выходных данных Для каждого тестового случая в отдельной строке выведите количество различных компьютеров, чей номер не зависит от выбора нумерации компьютеров, удовлетворяющей описанным в условии критериям. Пример
Для отправки решений необходимо выполнить вход. |