Боб и Кэрол провели целый день вместе с Алисой, но пришла пора идти домой. Алиса, Боб и Кэрол живут на бесконечной двумерной плоскости в клетках $$$A$$$, $$$B$$$ и $$$C$$$ соответственно. Сейчас все трое находятся в клетке $$$A$$$.
Если Боб (или Кэрол) находится в некоторой клетке, то он (она) может переместиться в одну из ее соседних клеток. Две клетки называются соседними, если они имеют общую сторону. Например, у клетки $$$(3, 5)$$$ есть четыре соседние клетки: $$$(2, 5)$$$, $$$(4, 5)$$$, $$$(3, 6)$$$ и $$$(3, 4)$$$.
Боб хочет вернуться в клетку $$$B$$$, Кэрол — в клетку $$$C$$$. Каждый из них хочет вернуться домой по кратчайшему пути, т. е. по пути, который состоит из наименьшего возможного количества клеток. Но также они хотели бы идти вместе.
Какое наибольшее возможное количество клеток Боб и Кэрол смогут пройти вместе, если каждых из них идет домой по одному из кратчайших путей?
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных заданы два целых числа $$$x_A$$$ и $$$y_A$$$ ($$$1 \le x_A, y_A \le 10^8$$$) — позиция клетки $$$A$$$, где сейчас находятся Боб и Кэрол.
Во второй строке каждого набора заданы два целых числа $$$x_B$$$ и $$$y_B$$$ ($$$1 \le x_B, y_B \le 10^8$$$) — позиция клетки $$$B$$$ (дом Боба).
В третьей строке каждого набора заданы два целых числа $$$x_C$$$ и $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) — позиция клетки $$$C$$$ (дом Кэрол).
Дополнительное ограничение на входные данные: в пределах одного набора клетки $$$A$$$, $$$B$$$ $$$C$$$ — попарно различные.
Для каждого набора входных данных, выведите одно целое число — максимально возможное количество клеток, которые Боб и Кэрол могут пройти вместе, если каждый из них идет домой по одному из кратчайших путей.
33 11 36 45 22 27 21 14 35 5
3 1 6
Во всех картинках, красным обозначены клетки, лежащие только на пути Боба; светло-синим — клетки на пути только Кэрол, а темно-синим — общие для Боба и Кэрол клетки.
Один из оптимальных ответов для первого набора входных данных изображен ниже:
Оптимальный ответ для второго набора изоборажен ниже:
Один из оптимальных ответов для третьего набора изображен ниже:
