На сайте БрутФорсез решили провести новый формат командных соревнований: все тесты к задачам открытые, и в одной команде может быть произвольное количество участников. Итоговая добавка к рейтингу, конечно же, поровну разделяется между всеми членами команды.

На первом же контесте организаторы предложили следующую непростую задачу:

«Дана таблица $$$S$$$ размера $$$m \times n$$$. В клетке $$$S_{i, j}$$$ (где $$$1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n$$$) написана сумма чисел от $$$1$$$ до $$$i+j$$$. Для заданных чисел $$$a, b$$$ выведите сумму по подтаблице с угловыми клетками $$$S_{1, 1}$$$ и $$$S_{a, b}$$$».

Всего к этой задаче было составлено $$$T$$$ тестов.

Прочитав условие задачи, синий кодер Вася быстро сообразил, как ее решать — если бы мы знали, какое число написано в каждой из клеток, то алгоритмом решения было бы обыкновенное дерево Фенвика!

Дело осталось за малым — надо найти значение в необходимых клетках доски (но не обязательно во всех). Для этого он решил позвать в свою команду нескольких зеленых кодеров, чтобы дать каждому по клетке $$$S_{i, j}$$$ и попросить посчитать число в ней. Так как итоговая добавка к рейтингу поровну делится между членами команды, Вася хочет пригласить как можно меньше кодеров, а потому посчитать числа только в тех клетках, которые нужны для вычисления ответа в хотя бы одном из тестов (то есть, которые содержатся хотя бы в одной подтаблице).

Какое минимальное число кодеров ему надо пригласить в команду, чтобы осуществить задуманное?