A. Shortest Path with Obstacle

problem_index: A

time_limit: 2 seconds

memory_limit: 512 megabytes

note:
![image](images/cf_1547_A/1.png) An example of a possible shortest path for the first test case.
![image](images/cf_1547_A/2.png) An example of a possible shortest path for the second test case.

solutions: ["t = int(input())\na = []\nfor i in range(t):\n\tblank = list(map(str, input().split()))\n\tx = list(map(int, input().split()))\n\ty = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\tif x[0] == y[0] and x[0] == f[0]:\n\t\tif (f[1] - x[1]) * (f[1] - y[1]) < 0:\n\t\t\tn = abs(y[1] - x[1]) + 2\n\t\telse:\n\t\t\tn = abs(y[1] - x[1])\n\telif x[1] == y[1] and x[1] == f[1]:\n\t\tif (f[0] - x[0]) * (f[0] - y[0]) < 0:\n\t\t\tn = abs(y[0] - x[0]) + 2\n\t\telse:\n\t\t\tn = abs(y[0] - x[0])\n\telse:\n\t\tn = abs(y[0] - x[0]) + abs(y[1] - x[1])\n\ta.append(n)\nfor i in range(t):\n\tprint(a[i])\n", "def pro(A, B, F):\n\t(x, y) = A\n\t(p, q) = F\n\t(x1, y1) = B\n\tans = 0\n\tif y == q == B[1] and min(x, x1) < p < max(x1, x):\n\t\ty += 1\n\t\tans += 1\n\telif x == p == x1 and min(y, y1) < q < max(y1, y):\n\t\tx += 1\n\t\tans += 1\n\tans += abs(x - x1) + abs(y - y1)\n\tprint(ans)\nt = int(input())\nfor i in range(t):\n\tinput()\n\tA = list(map(int, input().split()))\n\tB = list(map(int, input().split()))\n\tF = list(map(int, input().split()))\n\tpro(A, B, F)\n", "t = int(input())\nnothing = ''\nfor _ in range(0, t):\n\tnothing = input()\n\txa = xb = xf = ya = yb = yf = 0\n\t(xa, ya) = input().split()\n\t(xb, yb) = input().split()\n\t(xf, yf) = input().split()\n\t(xa, xb, xf, ya, yb, yf) = (int(xa), int(xb), int(xf), int(ya), int(yb), int(yf))\n\tdiffx = xa - xb\n\tdiffy = ya - yb\n\tif diffx < 0:\n\t\tdiffx = -diffx\n\tif diffy < 0:\n\t\tdiffy = -diffy\n\tresult = diffx + diffy\n\tif xa == xb == xf:\n\t\tif ya <= yf <= yb or ya >= yf >= yb:\n\t\t\tresult += 2\n\telif ya == yb == yf:\n\t\tif xa <= xf <= xb or xa >= xf >= xb:\n\t\t\tresult += 2\n\tprint(result)\n", "t = int(input())\nfor _ in range(t):\n\ti = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa == xb == xf and min(ya, yb) < yf < max(ya, yb):\n\t\tans = abs(ya - yb) + 2\n\telif ya == yb == yf and min(xa, xb) < xf < max(xa, xb):\n\t\tans = abs(xa - xb) + 2\n\telse:\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nT = int(input())\ninput()\nfor _ in range(T):\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tanswer = -1\n\ttemp = 0\n\tif xa == xb == xf:\n\t\tif ya < yf < yb or yb < yf < ya:\n\t\t\ttemp = 2\n\telif ya == yb == yf:\n\t\tif xa < xf < xb or xb < xf < xa:\n\t\t\ttemp = 2\n\tanswer = temp + abs(xa - xb) + abs(ya - yb)\n\tprint(answer)\n\tinput()\n", "for t in range(int(input())):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tres = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb == xf:\n\t\tif yf in range(min(ya, yb), max(ya, yb)):\n\t\t\tres += 2\n\tif ya == yb == yf:\n\t\tif xf in range(min(xa, xb), max(xa, xb)):\n\t\t\tres += 2\n\tprint(res)\n", "n = int(input())\nfor i in range(n):\n\tinput()\n\t(ax, ay) = [int(i) for i in input().split()]\n\t(bx, by) = [int(i) for i in input().split()]\n\t(fx, fy) = [int(i) for i in input().split()]\n\tans = abs(ax - bx) + abs(ay - by)\n\tif ax == bx and ax == fx:\n\t\tif min(ay, by) < fy and fy < max(ay, by):\n\t\t\tans += 2\n\telif ay == by and ay == fy:\n\t\tif min(ax, bx) < fx and fx < max(ax, bx):\n\t\t\tans += 2\n\tprint(ans)\n", "from math import *\n\ndef sol(A, B, F):\n\tif A[0] == B[0]:\n\t\tif min(A[1], B[1]) < F[1] < max(A[1], B[1]) and F[0] == A[0]:\n\t\t\tprint(abs(A[1] - B[1]) + abs(A[0] - B[0]) + 2)\n\t\telse:\n\t\t\tprint(abs(A[1] - B[1]) + abs(A[0] - B[0]))\n\telif A[1] == B[1]:\n\t\tif min(A[0], B[0]) < F[0] < max(A[0], B[0]) and F[1] == A[1]:\n\t\t\tprint(abs(A[1] - B[1]) + abs(A[0] - B[0]) + 2)\n\t\telse:\n\t\t\tprint(abs(A[1] - B[1]) + abs(A[0] - B[0]))\n\telse:\n\t\tprint(abs(A[1] - B[1]) + abs(A[0] - B[0]))\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tx = input()\n\t\tA = list(map(int, input().split()))\n\t\tB = list(map(int, input().split()))\n\t\tF = list(map(int, input().split()))\n\t\tsol(A, B, F)\nmain()\n", "for r in range(int(input())):\n\tinput()\n\t(xa, ya) = list(map(int, input().split()))\n\t(xb, yb) = list(map(int, input().split()))\n\t(xf, yf) = list(map(int, input().split()))\n\tif xa == xb:\n\t\tif (ya < yf < yb or ya > yf > yb) and xa == xf:\n\t\t\tprint(abs(yb - ya) + 2)\n\t\telse:\n\t\t\tprint(abs(yb - ya))\n\telif ya == yb:\n\t\tif (xa < xf < xb or xa > xf > xb) and ya == yf:\n\t\t\tprint(abs(xb - xa) + 2)\n\t\telse:\n\t\t\tprint(abs(xb - xa))\n\telse:\n\t\tprint(abs(xb - xa) + abs(yb - ya))\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tans = abs(xa - xb) + abs(ya - yb)\n\ttmp = 0\n\tif xa == xb == xf and (yf - ya) * (yf - yb) < 0:\n\t\ttmp = 2\n\tif ya == yb == yf and (xf - xa) * (xf - xb) < 0:\n\t\ttmp = 2\n\tprint(ans + tmp)\n", "n = int(input())\nfor i in range(n):\n\tx_A = 0\n\tx_B = 0\n\ty_A = 0\n\ty_B = 0\n\tx_F = 0\n\ty_F = 0\n\ts = input()\n\ts = input().split()\n\tx_A = int(s[0])\n\ty_A = int(s[1])\n\ts = input().split()\n\tx_B = int(s[0])\n\ty_B = int(s[1])\n\ts = input().split()\n\tx_F = int(s[0])\n\ty_F = int(s[1])\n\tif x_A == x_B == x_F and (y_A > y_F > y_B or y_B > y_F > y_A):\n\t\tprint(abs(y_A - y_B) + 2)\n\telif y_A == y_B == y_F and (x_A > x_F > x_B or x_B > x_F > x_A):\n\t\tprint(abs(x_A - x_B) + 2)\n\telse:\n\t\tprint(abs(x_A - x_B) + abs(y_A - y_B))\n", "for t in range(int(input())):\n\ts = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 == x3 and y1 == y3 or (x2 == x3 and y2 == y3):\n\t\tprint(-1)\n\t\tcontinue\n\telif x1 == x2 and y1 == y2:\n\t\tprint(0)\n\telif x1 == x2:\n\t\tval = abs(y2 - y1)\n\t\tif x3 == x1 and y3 > min(y2, y1) and (y3 < max(y2, y1)):\n\t\t\tval += 2\n\t\tprint(val)\n\t\tcontinue\n\telif y1 == y2:\n\t\tval = abs(x1 - x2)\n\t\tif y3 == y1 and x3 > min(x1, x2) and (x3 < max(x1, x2)):\n\t\t\tval += 2\n\t\tprint(val)\n\t\tcontinue\n\telse:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n", "for _ in range(int(input())):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif ya == yb == yf and (xa < xf) != (xb < xf) or (xa == xb == xf and (ya < yf) != (yb < yf)):\n\t\tprint(2 + abs(xa - xb) + abs(ya - yb))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "res = []\ntests = int(input())\nfor j in range(tests):\n\ta = input().split()\n\tb = input().split()\n\tc = input().split()\n\td = input().split()\n\t(a1, a2, b1, b2, f1, f2) = (int(b[0]), int(b[1]), int(c[0]), int(c[1]), int(d[0]), int(d[1]))\n\tif a1 == b1 == f1 and f2 != min(a2, b2, f2) and (f2 != max(a2, b2, f2)):\n\t\tres.append(abs(a2 - b2) + 2)\n\telif a2 == b2 == f2 and f1 != min(a1, b1, f1) and (f1 != max(a1, b1, f1)):\n\t\tres.append(abs(a1 - b1) + 2)\n\telse:\n\t\tres.append(abs(a1 - b1) + abs(a2 - b2))\nfor i in res:\n\tprint(i)\n", "from sys import stdin, stdout\n\ndef solve(ax, ay, bx, by, fx, fy):\n\trx = abs(ax - bx)\n\try = abs(ay - by)\n\tif ax == bx or ay == by:\n\t\te = 0\n\t\tif fx in range(min(ax, bx), max(ax, bx) + 1):\n\t\t\tif fy == ay:\n\t\t\t\te += 2\n\t\tif fy in range(min(ay, by), max(ay, by) + 1):\n\t\t\tif fx == ax:\n\t\t\t\te += 2\n\t\treturn rx + ry + e\n\treturn rx + ry\nt = int(input())\nfor _ in range(t):\n\tblank = input()\n\tif blank != '':\n\t\tbreak\n\t(ax, ay) = [int(c) for c in input().split()]\n\t(bx, by) = [int(c) for c in input().split()]\n\t(fx, fy) = [int(c) for c in input().split()]\n\tprint(solve(ax, ay, bx, by, fx, fy))\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tinput()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(cx, cy) = map(int, input().split())\n\tres = abs(ax - bx) + abs(ay - by)\n\tif ax == bx == cx and cy in range(min(ay, by), max(ay, by)):\n\t\tres += 2\n\tif ay == by == cy and cx in range(min(ax, bx), max(ax, bx)):\n\t\tres += 2\n\tprint(res)\n", "for _ in range(int(input())):\n\tinput()\n\t(x_a, y_a) = input().split()\n\t(x_a, y_a) = (int(x_a), int(y_a))\n\t(x_b, y_b) = input().split()\n\t(x_b, y_b) = (int(x_b), int(y_b))\n\t(x_f, y_f) = input().split()\n\t(x_f, y_f) = (int(x_f), int(y_f))\n\tanswer = abs(x_a - x_b) + abs(y_a - y_b)\n\tif x_a == x_b == x_f and min(y_a, y_b) < y_f < max(y_a, y_b) or (y_a == y_b == y_f and min(x_a, x_b) < x_f < max(x_a, x_b)):\n\t\tanswer += 2\n\tprint(answer)\n", "t = int(input())\nA = []\nfor zxc_ghoul in range(t):\n\tnone = input()\n\t(x_a, y_a) = map(int, input().split())\n\t(x_b, y_b) = map(int, input().split())\n\t(x_f, y_f) = map(int, input().split())\n\tif x_a == x_b or y_a == y_b:\n\t\tif x_a == x_b:\n\t\t\tif x_a == x_f and (y_a > y_f and y_f > y_b or (y_f > y_a and y_f < y_b)):\n\t\t\t\tans = abs(y_a - y_b) + 2\n\t\t\telse:\n\t\t\t\tans = abs(y_a - y_b)\n\t\tif y_a == y_b:\n\t\t\tif y_a == y_f and (x_a > x_f and x_f > x_b or (x_f > x_a and x_f < x_b)):\n\t\t\t\tans = abs(x_a - x_b) + 2\n\t\t\telse:\n\t\t\t\tans = abs(x_a - x_b)\n\telse:\n\t\tans = abs(x_a - x_b) + abs(y_a - y_b)\n\tA.append(ans)\nfor i in A:\n\tprint(i)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nreadint = lambda : int(sys.stdin.readline().rstrip('\\r\\n'))\nreadints = lambda : map(int, sys.stdin.readline().rstrip('\\r\\n').split())\nreadstr = lambda : sys.stdin.readline().rstrip('\\r\\n')\nreadstrs = lambda : map(str, sys.stdin.readline().rstrip('\\r\\n').split())\nreadarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\\r\\n').split()]\nreadarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\\r\\n').split()]\n\ndef solve():\n\ta = readstr()\n\t(ax, ay) = readints()\n\t(cx, cy) = readints()\n\t(bx, by) = readints()\n\tmanhattan = abs(ax - cx) + abs(ay - cy)\n\tif ay == cy or ax == cx:\n\t\tif ax == cx == bx and (ay <= by <= cy or ay >= by >= cy) or (ay == cy == by and (ax <= bx <= cx or ax >= bx >= cx)):\n\t\t\tmanhattan += 2\n\tprint(manhattan)\n\ndef main():\n\tt = 1\n\tt = readint()\n\tfor _ in range(t):\n\t\tsolve()\nmain()\n", "import os\nimport sys\nfrom math import ceil, floor, sqrt, gcd, factorial\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tinput()\n\t\t(xa, ya) = map(int, input().split())\n\t\t(xb, yb) = map(int, input().split())\n\t\t(xf, yf) = map(int, input().split())\n\t\tif xa == xb == xf and yf < max(yb, ya) and (yf > min(yb, ya)):\n\t\t\tprint(abs(xb - xa) + abs(yb - ya) + 2)\n\t\telif ya == yb == yf and xf < max(xb, xa) and (xf > min(xb, xa)):\n\t\t\tprint(abs(xb - xa) + abs(yb - ya) + 2)\n\t\telse:\n\t\t\tprint(abs(xb - xa) + abs(yb - ya))\nmain()\n", "t = int(input())\np = 0\nwhile p < t:\n\tinput()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\tif ay == by == fy and (ax > fx > bx or ax < fx < bx):\n\t\tprint(abs(ax - bx) + 2)\n\telif ax == bx == fx and (ay > fy > by or ay < fy < by):\n\t\tprint(abs(ay - by) + 2)\n\telse:\n\t\tprint(abs(ax - bx) + abs(ay - by))\n\tp += 1\n", "import os\nimport sys\nimport math\nfrom io import BytesIO, IOBase\nimport io\nfrom fractions import Fraction\nimport collections\nfrom itertools import permutations\nfrom collections import defaultdict\nfrom collections import deque\nfrom collections import Counter\nimport threading\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\nclass SegmentTree:\n\n\tdef __init__(self, data, default=0, func=lambda a, b: max(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree1:\n\n\tdef __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\nMOD = 10 ** 9 + 7\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\nmod = 10 ** 9 + 7\nomod = 998244353\nprime = [True for i in range(10001)]\nprime[0] = prime[1] = False\n\ndef SieveOfEratosthenes(n=10000):\n\tp = 2\n\tc = 0\n\twhile p <= n:\n\t\tif prime[p] == True:\n\t\t\tc += 1\n\t\t\tfor i in range(p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\nclass DSU:\n\n\tdef __init__(self, R, C):\n\t\tself.par = range(R * C + 1)\n\t\tself.rnk = [0] * (R * C + 1)\n\t\tself.sz = [1] * (R * C + 1)\n\n\tdef find(self, x):\n\t\tif self.par[x] != x:\n\t\t\tself.par[x] = self.find(self.par[x])\n\t\treturn self.par[x]\n\n\tdef union(self, x, y):\n\t\t(xr, yr) = (self.find(x), self.find(y))\n\t\tif xr == yr:\n\t\t\treturn\n\t\tif self.rnk[xr] < self.rnk[yr]:\n\t\t\t(xr, yr) = (yr, xr)\n\t\tif self.rnk[xr] == self.rnk[yr]:\n\t\t\tself.rnk[xr] += 1\n\t\tself.par[yr] = xr\n\t\tself.sz[xr] += self.sz[yr]\n\n\tdef size(self, x):\n\t\treturn self.sz[self.find(x)]\n\n\tdef top(self):\n\t\treturn self.size(len(self.sz) - 1) - 1\n\nclass LazySegTree:\n\n\tdef __init__(self, _op, _e, _mapping, _composition, _id, v):\n\n\t\tdef set(p, x):\n\t\t\tassert 0 <= p < _n\n\t\t\tp += _size\n\t\t\tfor i in range(_log, 0, -1):\n\t\t\t\t_push(p >> i)\n\t\t\t_d[p] = x\n\t\t\tfor i in range(1, _log + 1):\n\t\t\t\t_update(p >> i)\n\n\t\tdef get(p):\n\t\t\tassert 0 <= p < _n\n\t\t\tp += _size\n\t\t\tfor i in range(_log, 0, -1):\n\t\t\t\t_push(p >> i)\n\t\t\treturn _d[p]\n\n\t\tdef prod(l, r):\n\t\t\tassert 0 <= l <= r <= _n\n\t\t\tif l == r:\n\t\t\t\treturn _e\n\t\t\tl += _size\n\t\t\tr += _size\n\t\t\tfor i in range(_log, 0, -1):\n\t\t\t\tif l >> i << i != l:\n\t\t\t\t\t_push(l >> i)\n\t\t\t\tif r >> i << i != r:\n\t\t\t\t\t_push(r >> i)\n\t\t\tsml = _e\n\t\t\tsmr = _e\n\t\t\twhile l < r:\n\t\t\t\tif l & 1:\n\t\t\t\t\tsml = _op(sml, _d[l])\n\t\t\t\t\tl += 1\n\t\t\t\tif r & 1:\n\t\t\t\t\tr -= 1\n\t\t\t\t\tsmr = _op(_d[r], smr)\n\t\t\t\tl >>= 1\n\t\t\t\tr >>= 1\n\t\t\treturn _op(sml, smr)\n\n\t\tdef apply(l, r, f):\n\t\t\tassert 0 <= l <= r <= _n\n\t\t\tif l == r:\n\t\t\t\treturn\n\t\t\tl += _size\n\t\t\tr += _size\n\t\t\tfor i in range(_log, 0, -1):\n\t\t\t\tif l >> i << i != l:\n\t\t\t\t\t_push(l >> i)\n\t\t\t\tif r >> i << i != r:\n\t\t\t\t\t_push(r - 1 >> i)\n\t\t\tl2 = l\n\t\t\tr2 = r\n\t\t\twhile l < r:\n\t\t\t\tif l & 1:\n\t\t\t\t\t_all_apply(l, f)\n\t\t\t\t\tl += 1\n\t\t\t\tif r & 1:\n\t\t\t\t\tr -= 1\n\t\t\t\t\t_all_apply(r, f)\n\t\t\t\tl >>= 1\n\t\t\t\tr >>= 1\n\t\t\tl = l2\n\t\t\tr = r2\n\t\t\tfor i in range(1, _log + 1):\n\t\t\t\tif l >> i << i != l:\n\t\t\t\t\t_update(l >> i)\n\t\t\t\tif r >> i << i != r:\n\t\t\t\t\t_update(r - 1 >> i)\n\n\t\tdef _update(k):\n\t\t\t_d[k] = _op(_d[2 * k], _d[2 * k + 1])\n\n\t\tdef _all_apply(k, f):\n\t\t\t_d[k] = _mapping(f, _d[k])\n\t\t\tif k < _size:\n\t\t\t\t_lz[k] = _composition(f, _lz[k])\n\n\t\tdef _push(k):\n\t\t\t_all_apply(2 * k, _lz[k])\n\t\t\t_all_apply(2 * k + 1, _lz[k])\n\t\t\t_lz[k] = _id\n\t\t_n = len(v)\n\t\t_log = _n.bit_length()\n\t\t_size = 1 << _log\n\t\t_d = [_e] * (2 * _size)\n\t\t_lz = [_id] * _size\n\t\tfor i in range(_n):\n\t\t\t_d[_size + i] = v[i]\n\t\tfor i in range(_size - 1, 0, -1):\n\t\t\t_update(i)\n\t\tself.set = set\n\t\tself.get = get\n\t\tself.prod = prod\n\t\tself.apply = apply\nMIL = 1 << 20\n\ndef makeNode(total, count):\n\treturn total * MIL + count\n\ndef getTotal(node):\n\treturn math.floor(node / MIL)\n\ndef getCount(node):\n\treturn node - getTotal(node) * MIL\nnodeIdentity = makeNode(0.0, 0.0)\n\ndef nodeOp(node1, node2):\n\treturn node1 + node2\n\treturn makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))\nidentityMapping = -1\n\ndef mapping(tag, node):\n\tif tag == identityMapping:\n\t\treturn node\n\tcount = getCount(node)\n\treturn makeNode(tag * count, count)\n\ndef composition(mapping1, mapping2):\n\treturn mapping1 if mapping1 != identityMapping else mapping2\n\ndef memodict(f):\n\n\tclass memodict(dict):\n\n\t\tdef __missing__(self, key):\n\t\t\tret = self[key] = f(key)\n\t\t\treturn ret\n\treturn memodict().__getitem__\n\ndef pollard_rho(n):\n\tif n & 1 == 0:\n\t\treturn 2\n\tif n % 3 == 0:\n\t\treturn 3\n\ts = (n - 1 & 1 - n).bit_length() - 1\n\td = n >> s\n\tfor a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:\n\t\tp = pow(a, d, n)\n\t\tif p == 1 or p == n - 1 or a % n == 0:\n\t\t\tcontinue\n\t\tfor _ in range(s):\n\t\t\tprev = p\n\t\t\tp = p * p % n\n\t\t\tif p == 1:\n\t\t\t\treturn math.gcd(prev - 1, n)\n\t\t\tif p == n - 1:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tfor i in range(2, n):\n\t\t\t\t(x, y) = (i, (i * i + 1) % n)\n\t\t\t\tf = math.gcd(abs(x - y), n)\n\t\t\t\twhile f == 1:\n\t\t\t\t\t(x, y) = ((x * x + 1) % n, (y * y + 1) % n)\n\t\t\t\t\ty = (y * y + 1) % n\n\t\t\t\t\tf = math.gcd(abs(x - y), n)\n\t\t\t\tif f != n:\n\t\t\t\t\treturn f\n\treturn n\n\n@memodict\ndef prime_factors(n):\n\tif n <= 1:\n\t\treturn Counter()\n\tf = pollard_rho(n)\n\treturn Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)\n\ndef distinct_factors(n):\n\tfactors = [1]\n\tfor (p, exp) in prime_factors(n).items():\n\t\tfactors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]\n\treturn factors\n\ndef all_factors(n):\n\t(small, large) = ([], [])\n\tfor i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):\n\t\tif not n % i:\n\t\t\tsmall.append(i)\n\t\t\tlarge.append(n // i)\n\tif small[-1] == large[-1]:\n\t\tlarge.pop()\n\tlarge.reverse()\n\tsmall.extend(large)\n\treturn small\n\ndef binarySearch(arr, n, key):\n\tleft = 0\n\tright = n - 1\n\tmid = 0\n\tres = arr[n - 1]\n\twhile left <= right:\n\t\tmid = (right + left) // 2\n\t\tif arr[mid] >= key:\n\t\t\tres = arr[mid]\n\t\t\tright = mid - 1\n\t\telse:\n\t\t\tleft = mid + 1\n\treturn res\n\ndef binarySearch1(arr, n, key):\n\tleft = 0\n\tright = n - 1\n\tmid = 0\n\tres = -1\n\twhile left <= right:\n\t\tmid = (right + left) // 2\n\t\tif arr[mid][0] >= key:\n\t\t\tright = mid - 1\n\t\telse:\n\t\t\tres = mid\n\t\t\tleft = mid + 1\n\treturn res\nt = 1\nt = int(input())\nfor _ in range(t):\n\tx = input()\n\t(a, b) = map(int, input().split())\n\t(c, d) = map(int, input().split())\n\t(e, f) = map(int, input().split())\n\tdist = abs(a - c) + abs(b - d)\n\tif a == c == e and f > min(b, d) and (f < max(b, d)):\n\t\tdist += 2\n\telif b == d == f and e > min(a, c) and (e < max(a, c)):\n\t\tdist += 2\n\tprint(dist)\n", "t = int(input())\nfor _ in range(t):\n\t_ = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tans = abs(xb - xa) + abs(yb - ya)\n\tif xa == xb and xb == xf:\n\t\tif yf > ya and yf < yb or (yf > yb and yf < ya):\n\t\t\tans += 2\n\telif ya == yb and yb == yf:\n\t\tif xf > xa and xf < xb or (xf > xb and xf < xa):\n\t\t\tans += 2\n\tprint(ans)\n", "l = ''.join([*open(0)]).split('\\n\\n')[1:]\nfor i in l:\n\t(a, b, c, d, e, f) = map(int, i.split())\n\tn = abs(a - c) + abs(b - d)\n\tif a == c == e and b < f < d or (a == c == e and d < f < b) or (b == d == f and a < e < c) or (b == d == f and c < e < a):\n\t\tprint(n + 2)\n\telse:\n\t\tprint(n)\n", "a = int(input())\nmas = []\nfor i in range(a):\n\tinput()\n\tmass = []\n\tmass.append(input().split())\n\tmass[0][0] = int(mass[0][0])\n\tmass[0][1] = int(mass[0][1])\n\tmass.append(input().split())\n\tmass[1][0] = int(mass[1][0])\n\tmass[1][1] = int(mass[1][1])\n\tmass.append(input().split())\n\tmass[2][0] = int(mass[2][0])\n\tmass[2][1] = int(mass[2][1])\n\tmas.append(mass)\nfor i in mas:\n\tlex = abs(i[0][0] - i[1][0])\n\tley = abs(i[0][1] - i[1][1])\n\tle = lex + ley\n\tif lex == 0 and i[2][0] == i[0][0] and (i[2][1] > min(i[0][1], i[1][1])) and (i[2][1] < max(i[0][1], i[1][1])):\n\t\tle += 2\n\tif ley == 0 and i[2][1] == i[0][1] and (i[2][0] > min(i[0][0], i[1][0])) and (i[2][0] < max(i[0][0], i[1][0])):\n\t\tle += 2\n\tprint(le)\n", "t = int(input())\nanslist = []\nfor i in range(t):\n\tinp = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(f1, f2) = map(int, input().split())\n\tif x1 != x2 and y1 != y2:\n\t\tanslist.append(abs(x2 - x1) + abs(y2 - y1))\n\telif x1 == x2:\n\t\tif f1 == x1:\n\t\t\tif f2 > y1 and f2 < y2:\n\t\t\t\tanslist.append(abs(y2 - y1) + 2)\n\t\t\telif f2 < y1 and f2 > y2:\n\t\t\t\tanslist.append(abs(y2 - y1) + 2)\n\t\t\telse:\n\t\t\t\tanslist.append(abs(y2 - y1))\n\t\telse:\n\t\t\tanslist.append(abs(y2 - y1))\n\telif y1 == y2:\n\t\tif f2 == y1:\n\t\t\tif f1 > x1 and f1 < x2:\n\t\t\t\tanslist.append(abs(x2 - x1) + 2)\n\t\t\t\tpass\n\t\t\telif f1 < x1 and f1 > x2:\n\t\t\t\tanslist.append(abs(x2 - x1) + 2)\n\t\t\telse:\n\t\t\t\tanslist.append(abs(x2 - x1))\n\t\telse:\n\t\t\tanslist.append(abs(x2 - x1))\nlength = len(anslist)\ny = 0\nfor i in range(length):\n\tprint(anslist[y])\n\ty += 1\n", "import sys\nimport collections\nimport bisect\nimport time\nimport random\nfrom itertools import permutations\nimport string\nimport math\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef get_list():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef get_string():\n\treturn sys.stdin.readline().strip()\ntc = int(input())\ninput()\nfor t in range(tc):\n\t(x1, y1) = get_ints()\n\t(x2, y2) = get_ints()\n\t(x3, y3) = get_ints()\n\tif t != tc - 1:\n\t\tinput()\n\tans = abs(x1 - x2) + abs(y1 - y2)\n\tminimy = min(y1, y2)\n\tmaximy = max(y1, y2)\n\tminimx = min(x1, x2)\n\tmaximx = max(x1, x2)\n\tif x1 == x2 == x3:\n\t\tif y3 >= minimy and y3 <= maximy:\n\t\t\tans += 2\n\telif y1 == y2 == y3:\n\t\tif x3 >= minimx and x3 <= maximx:\n\t\t\tans += 2\n\tprint(ans)\n", "import os, sys, time, collections, math, pprint, itertools as it, operator as op, bisect as bs, functools as fn\n(maxx, localsys, mod) = (1 << 60, 0, int(1000000000.0 + 7))\nnCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)\nceil = lambda n, x: (n + x - 1) // x\n(osi, oso) = ('/home/priyanshu/Documents/cp/input.txt', '/home/priyanshu/Documents/cp/output.txt')\nif os.path.exists(osi):\n\tsys.stdin = open(osi, 'r')\n\tsys.stdout = open(oso, 'w')\ninput = sys.stdin.readline\n\ndef maps():\n\treturn map(int, input().split())\nfor _ in range(int(input())):\n\tfor i in range(4):\n\t\tif i == 0:\n\t\t\tinput()\n\t\tif i == 1:\n\t\t\t(ax, ay) = list(maps())\n\t\tif i == 2:\n\t\t\t(bx, by) = list(maps())\n\t\tif i == 3:\n\t\t\t(fx, fy) = list(maps())\n\tdis = abs(ax - bx) + abs(ay - by)\n\tif ax == bx == fx and fy >= min(ay, by) and (fy <= max(ay, by)):\n\t\tprint(dis + 2)\n\telif ay == by == fy and fx >= min(ax, bx) and (fx <= max(ax, bx)):\n\t\tprint(dis + 2)\n\telse:\n\t\tprint(dis)\n", "import math\nfrom collections import deque, defaultdict\nfrom math import sqrt, ceil, factorial, floor, inf, gcd\nimport bisect\nimport sys\nimport random\nimport heapq\n\ndef get_array():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef input():\n\treturn sys.stdin.readline().strip()\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\nfor _ in range(int(input())):\n\t_ = input()\n\t(xa, ya) = get_ints()\n\t(xb, yb) = get_ints()\n\t(xc, yc) = get_ints()\n\tif xa == xb == xc and (ya > yc and yb < yc or (ya < yc and yb > yc)) or (ya == yb == yc and (xa > xc and xb < xc or (xa < xc and xb > xc))):\n\t\tprint(abs(xb - xa) + abs(yb - ya) + 2)\n\telse:\n\t\tprint(abs(xb - xa) + abs(yb - ya))\n", "t = int(input())\n\ndef is_between(a, b, f):\n\tmx = max(a, b)\n\tmn = min(a, b)\n\tif mn < f and f < mx:\n\t\treturn True\n\telse:\n\t\treturn False\nfor _t in range(t):\n\tinput()\n\t(xa, ya) = list(map(int, input().split()))\n\t(xb, yb) = list(map(int, input().split()))\n\t(xf, yf) = list(map(int, input().split()))\n\tif xa == xb:\n\t\tif xa == xf and is_between(ya, yb, yf):\n\t\t\tprint(abs(yb - ya) + 2)\n\t\telse:\n\t\t\tprint(abs(yb - ya))\n\telif ya == yb:\n\t\tif ya == yf and is_between(xa, xb, xf):\n\t\t\tprint(abs(xb - xa) + 2)\n\t\telse:\n\t\t\tprint(abs(xb - xa))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "from sys import stdin, setrecursionlimit\nfrom collections import defaultdict\nsetrecursionlimit(10 ** 7)\nfor _ in range(int(stdin.readline())):\n\tx = stdin.readline()\n\t(ax, ay) = map(int, stdin.readline().split())\n\t(bx, by) = map(int, stdin.readline().split())\n\t(fx, fy) = map(int, stdin.readline().split())\n\tif (fx == ax == bx or fy == ay == by) and (ax < fx < bx or ax > fx > bx or ay < fy < by or (ay > fy > by)):\n\t\tprint(abs(ax - bx) + abs(ay - by) + 2)\n\telse:\n\t\tprint(abs(ax - bx) + abs(ay - by))\n", "for s in ''.join(open(0)).split('\\n\\n')[1:]:\n\t(a, b, c, d, e, f) = map(int, s.split())\n\tprint(abs(a - c) + abs(b - d) + 2 * (a == c == e and (b < f < d or d < f < b) or (b == d == f and (a < e < c or c < e < a))))\n", "import sys, math\nsys.setrecursionlimit(10 ** 6)\nmod = 10 ** 9 + 7\ninput = lambda : sys.stdin.readline().rstrip()\n\ndef li():\n\treturn list(map(int, input().split()))\nt = int(input())\na = []\nfor _ in range(t):\n\tinput()\n\t(sx, sy) = li()\n\t(tx, ty) = li()\n\t(fx, fy) = li()\n\tans = abs(sx - tx) + abs(sy - ty)\n\tif sx == tx == fx and (sy < fy < ty or ty < fy < sy):\n\t\tans += 2\n\telif sy == ty == fy and (sx < fx < tx or tx < fx < sx):\n\t\tans += 2\n\ta.append(ans)\nfor ans in a:\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\ttemp = input()\n\t(Xa, Ya) = [int(x) for x in input().split()]\n\t(Xb, Yb) = [int(x) for x in input().split()]\n\t(Xc, Yc) = [int(x) for x in input().split()]\n\tif Xa == Xb == Xc and Yc < max(Ya, Yb) and (Yc > min(Ya, Yb)) or (Ya == Yb == Yc and Xc < max(Xa, Xb) and (Xc > min(Xa, Xb))):\n\t\tresult = abs(Xa - Xb) + abs(Ya - Yb) + 2\n\telse:\n\t\tresult = abs(Xa - Xb) + abs(Ya - Yb)\n\tprint(result)\n", "t = int(input())\nfor i in range(t):\n\tinput()\n\t(xa, ya) = list(map(int, input().split()))\n\t(xb, yb) = list(map(int, input().split()))\n\t(xf, yf) = list(map(int, input().split()))\n\tans = 0\n\tif xa == xb:\n\t\tif xf != xb:\n\t\t\tans = abs(ya - yb)\n\t\telif yf < min(ya, yb) or yf > max(ya, yb):\n\t\t\tans = abs(ya - yb)\n\t\telse:\n\t\t\tans = abs(ya - yb) + 2\n\telif ya == yb:\n\t\tif yf != yb:\n\t\t\tans = abs(xa - xb)\n\t\telif xf < min(xa, xb) or xf > max(xa, xb):\n\t\t\tans = abs(xa - xb)\n\t\telse:\n\t\t\tans = abs(xa - xb) + 2\n\telse:\n\t\tans = abs(ya - yb) + abs(xa - xb)\n\tprint(ans)\n", "from collections import deque, defaultdict, Counter, OrderedDict\nfrom sys import stdin, stdout\nimport bisect\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nimport itertools\nfrom collections import Counter\nfrom math import sqrt\nimport collections\nimport math\nimport heapq\nimport re\nfrom statistics import mode\n\ndef nCr(n, r):\n\treturn fact(n) // (fact(r) * fact(n - r))\n\ndef fact(n):\n\tres = 1\n\tfor i in range(2, n + 1):\n\t\tres = res * i\n\treturn res\n\ndef modinv(n, p):\n\treturn pow(n, p - 2, p)\n\ndef cin():\n\treturn map(int, sin().split())\n\ndef ain():\n\treturn list(map(int, sin().split()))\n\ndef sin():\n\treturn input()\n\ndef inin():\n\treturn int(input())\n\ndef Divisors(n):\n\tl = []\n\tfor i in range(1, int(math.sqrt(n) + 1)):\n\t\tif n % i == 0:\n\t\t\tif n // i == i:\n\t\t\t\tl.append(i)\n\t\t\telse:\n\t\t\t\tl.append(i)\n\t\t\t\tl.append(n // i)\n\treturn l\n\ndef most_frequent(list):\n\treturn max(set(list), key=list.count)\n\ndef GCD(x, y):\n\twhile y:\n\t\t(x, y) = (y, x % y)\n\treturn x\n\ndef ncr(n, r):\n\treturn fact[n] * pow(fact[r] * fact[n - r], mod - 2, mod) % mod\n\ndef Convert(string):\n\tli = list(string.split(''))\n\treturn li\n\ndef SieveOfEratosthenes(n):\n\tglobal prime\n\tprime = [True for i in range(n + 1)]\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p * p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\tf = []\n\tfor p in range(2, n):\n\t\tif prime[p]:\n\t\t\tf.append(p)\n\treturn f\nprime = []\n\ndef dfs(n, d, v, c):\n\tglobal q\n\tv[n] = 1\n\tx = d[n]\n\tq.append(n)\n\tj = c\n\tfor i in x:\n\t\tif i not in v:\n\t\t\tf = dfs(i, d, v, c + 1)\n\t\t\tj = max(j, f)\n\treturn j\n\ndef main():\n\tfor _ in range(inin()):\n\t\tlol = input()\n\t\t(x1, y1) = map(int, input().split())\n\t\t(x2, y2) = map(int, input().split())\n\t\t(x3, y3) = map(int, input().split())\n\t\tif x1 == x2 and x2 == x3 and (y3 > min(y1, y2)) and (y3 < max(y1, y2)):\n\t\t\tprint(abs(y2 - y1) + abs(x2 - x1) + 2)\n\t\telif y1 == y2 and y2 == y3 and (x3 > min(x1, x2)) and (x3 < max(x2, x1)):\n\t\t\tprint(abs(y2 - y1) + abs(x2 - x1) + 2)\n\t\telse:\n\t\t\tprint(abs(y2 - y1) + abs(x2 - x1))\npy2 = round(0.5)\nif py2:\n\tfrom future_builtins import ascii, filter, hex, map, oct, zip\n\trange = xrange\nimport os, sys\nfrom io import IOBase, BytesIO\nBUFSIZE = 8192\n\nclass FastIO(BytesIO):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._file = file\n\t\tself._fd = file.fileno()\n\t\tself.writable = 'x' in file.mode or 'w' in file.mode\n\t\tself.write = super(FastIO, self).write if self.writable else None\n\n\tdef _fill(self):\n\t\ts = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\tself.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])\n\t\treturn s\n\n\tdef read(self):\n\t\twhile self._fill():\n\t\t\tpass\n\t\treturn super(FastIO, self).read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\ts = self._fill()\n\t\t\tself.newlines = s.count(b'\\n') + (not s)\n\t\tself.newlines -= 1\n\t\treturn super(FastIO, self).readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.getvalue())\n\t\t\t(self.truncate(0), self.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tif py2:\n\t\t\tself.write = self.buffer.write\n\t\t\tself.read = self.buffer.read\n\t\t\tself.readline = self.buffer.readline\n\t\telse:\n\t\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "import sys\n\ndef get_string():\n\treturn sys.stdin.readline().strip()\n\ndef get_array():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef get_num():\n\treturn int(sys.stdin.readline())\nt = get_num()\nfor i in range(t):\n\ta = []\n\tfor j in range(4):\n\t\tx = get_array()\n\t\tif j > 0:\n\t\t\ta.append(x)\n\tdistance = abs(a[0][0] - a[1][0]) + abs(a[0][1] - a[1][1])\n\tif a[0][0] == a[1][0] == a[2][0] and a[0][1] < a[2][1] < a[1][1]:\n\t\tdistance += 2\n\telif a[0][1] == a[1][1] == a[2][1] and a[0][0] < a[2][0] < a[1][0]:\n\t\tdistance += 2\n\telif a[0][0] == a[1][0] == a[2][0] and a[0][1] > a[2][1] > a[1][1]:\n\t\tdistance += 2\n\telif a[0][1] == a[1][1] == a[2][1] and a[0][0] > a[2][0] > a[1][0]:\n\t\tdistance += 2\n\tprint(distance)\n", "def is_f_aligned(xA, yA, xB, yB, xF, yF):\n\tflag = False\n\tif xF == xA and xF == xB:\n\t\tif yF > min(yA, yB) and yF < max(yA, yB):\n\t\t\tflag = True\n\tif yF == yA and yF == yB:\n\t\tif xF > min(xA, xB) and xF < max(xA, xB):\n\t\t\tflag = True\n\treturn flag\nt = int(input())\nfor i in range(t):\n\tblank = input()\n\tpA = input()\n\tpB = input()\n\tpF = input()\n\tpA = list(map(int, pA.split(' ')))\n\tpB = list(map(int, pB.split(' ')))\n\tpF = list(map(int, pF.split(' ')))\n\tformula = lambda xA, yA, xB, yB: abs(xA - xB) + abs(yA - yB)\n\txA = pA[0]\n\tyA = pA[1]\n\txB = pB[0]\n\tyB = pB[1]\n\txF = pF[0]\n\tyF = pF[1]\n\tsteps = formula(xA, yA, xB, yB)\n\tif is_f_aligned(xA, yA, xB, yB, xF, yF) == True:\n\t\tprint(steps + 2)\n\telse:\n\t\tprint(steps)\n", "t = int(input())\nfor _ in range(t):\n\to = input()\n\t(a1, b1) = [int(i) for i in input().split()]\n\t(a2, b2) = [int(i) for i in input().split()]\n\t(a3, b3) = [int(i) for i in input().split()]\n\tif a1 != a2 and b1 != b2:\n\t\tprint(abs(a1 - a2) + abs(b1 - b2))\n\telif a1 == a2 == a3 and (b3 > b1 and b3 < b2 or (b3 > b2 and b3 < b1)):\n\t\tprint(abs(a1 - a2) + abs(b1 - b2) + 2)\n\telif b1 == b2 == b3 and (a3 > a1 and a3 < a2 or (a3 > a2 and a3 < a1)):\n\t\tprint(abs(a1 - a2) + abs(b1 - b2) + 2)\n\telse:\n\t\tprint(abs(a1 - a2) + abs(b1 - b2))\n", "import sys\nt = int(sys.stdin.readline())\nfor _ in range(t):\n\tsys.stdin.readline()\n\ta = list(map(int, sys.stdin.readline().split()))\n\tb = list(map(int, sys.stdin.readline().split()))\n\tf = list(map(int, sys.stdin.readline().split()))\n\tanswer = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\tif a[0] == b[0] == f[0]:\n\t\tif (a[1] - f[1]) * (b[1] - f[1]) < 0:\n\t\t\tanswer += 2\n\telif a[1] == b[1] == f[1]:\n\t\tif (a[0] - f[0]) * (b[0] - f[0]) < 0:\n\t\t\tanswer += 2\n\tprint(answer)\n", "for i in range(int(input())):\n\tinput()\n\t(ax, ay) = [int(x) for x in input().split()]\n\t(bx, by) = [int(x) for x in input().split()]\n\t(fx, fy) = [int(x) for x in input().split()]\n\tif ax == bx == fx and fy > min(ay, by) and (fy < max(by, ay)):\n\t\tprint(abs(bx - ax) + abs(by - ay) + 2)\n\telif ay == by == fy and fx > min(ax, bx) and (fx < max(ax, bx)):\n\t\tprint(abs(bx - ax) + abs(by - ay) + 2)\n\telse:\n\t\tprint(abs(bx - ax) + abs(by - ay))\n", "n = int(input())\nfor _ in range(n):\n\tinput()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\tif a[0] == b[0]:\n\t\td = abs(a[1] - b[1])\n\t\tif f[0] == a[0]:\n\t\t\tif abs(a[1] - f[1]) + abs(b[1] - f[1]) == abs(a[1] - b[1]):\n\t\t\t\td += 2\n\telif a[1] == b[1]:\n\t\td = abs(a[0] - b[0])\n\t\tif f[1] == a[1]:\n\t\t\tif abs(a[0] - f[0]) + abs(b[0] - f[0]) == abs(a[0] - b[0]):\n\t\t\t\td += 2\n\telse:\n\t\td = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\tprint(d)\n", "T = int(input())\nfor _ in range(T):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(cx, cy) = map(int, input().split())\n\td1 = abs(x1 - cx) + abs(y1 - cy)\n\td2 = abs(x2 - cx) + abs(y2 - cy)\n\td3 = abs(x2 - x1) + abs(y2 - y1)\n\tif (x1 == x2 == cx or y1 == y2 == cy) and d1 + d2 == d3:\n\t\tprint(d3 + 2)\n\telse:\n\t\tprint(d3)\n", "for i in range(int(input())):\n\tx = input()\n\t(a, b) = map(int, input().split())\n\t(c, d) = map(int, input().split())\n\t(e, f) = map(int, input().split())\n\tif a != c and b != d:\n\t\tprint(abs(a - c) + abs(b - d))\n\telif a == c and b != d:\n\t\tif a == e and (f > b and f < d or (f < b and f > d)):\n\t\t\tprint(abs(b - d) + 2)\n\t\telse:\n\t\t\tprint(abs(b - d))\n\telif a != c and b == d:\n\t\tif b == f and (e > a and e < c or (e < a and e > c)):\n\t\t\tprint(abs(a - c) + 2)\n\t\telse:\n\t\t\tprint(abs(a - c))\n\telse:\n\t\tprint(0)\n", "import sys\nimport math\nimport os.path\nfrom collections import *\nfrom queue import *\nfrom bisect import *\nfrom heapq import *\nMOD = int(1000000000.0 + 7)\ninf = float('inf')\nninf = float('-inf')\ninput = sys.stdin.buffer.readline\n\ndef ii():\n\treturn list(map(int, input().strip().split()))\n\ndef deb(a, b='Debugging'):\n\tprint(b, *a) if os.path.exists('inp.txt') else ''\nfor _ in range(int(input())):\n\tp = input()\n\t(a1, a2) = ii()\n\t(b1, b2) = ii()\n\t(f1, f2) = ii()\n\tif a1 == b1 and a1 == f1 and (a2 <= f2 <= b2 or b2 <= f2 <= a2):\n\t\tprint(abs(a2 - b2) + 2)\n\telif a2 == b2 and a2 == f2 and (a1 <= f1 <= b1 or b1 <= f1 <= a1):\n\t\tprint(abs(a1 - b1) + 2)\n\telse:\n\t\tprint(abs(a1 - b1) + abs(a2 - b2))\n", "t = int(input())\nfor _ in range(t):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tq1 = abs(xa - xb)\n\tq2 = abs(ya - yb)\n\tif q1 >= 1 and q2 >= 1:\n\t\tprint(q1 + q2)\n\telif q2 < 1:\n\t\tif yf == ya and (xf > xa and xf < xb or (xf < xa and xf > xb)):\n\t\t\tprint(q1 + q2 + 2)\n\t\telse:\n\t\t\tprint(q1 + q2)\n\telif xf == xa and (yf > ya and yf < yb or (yf < ya and yf > yb)):\n\t\tprint(q1 + q2 + 2)\n\telse:\n\t\tprint(q1 + q2)\n", "for i in range(int(input())):\n\tz = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa == ya and xb == yb:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\tcontinue\n\telif (xa == xb == xf or ya == yb == yf) and (xa < xf < xb or ya < yf < yb or xa > xf > xb or (ya > yf > yb)):\n\t\tprint(abs(xa - xb) + abs(ya - yb) + 2)\n\t\tcontinue\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\tcontinue\n", "import sys\nt = int(sys.stdin.readline())\n\ndef sol(st, ed, forbid):\n\t(xs, ys) = (st[0], st[1])\n\t(xe, ye) = (ed[0], ed[1])\n\t(xf, yf) = (forbid[0], forbid[1])\n\tif xs == xe and ys == ye:\n\t\treturn 0\n\tif xs == xe and xe == xf and (min(ys, ye) < yf) and (yf < max(ys, ye)) or (ys == ye and ye == yf and (min(xs, xe) < xf) and (xf < max(xs, xe))):\n\t\treturn 2 + abs(xe - xs) + abs(ye - ys)\n\telse:\n\t\treturn abs(xe - xs) + abs(ye - ys)\nfor i in range(t):\n\tcells = []\n\ta = sys.stdin.readline()\n\tst = list(map(int, sys.stdin.readline().split()))\n\ted = list(map(int, sys.stdin.readline().split()))\n\tforb = list(map(int, sys.stdin.readline().split()))\n\tprint(sol(st, ed, forb))\n", "import sys\ninput = sys.stdin.readline\n\ndef read():\n\treturn map(int, input().split())\n\ndef readarr():\n\treturn list(map(int, input().split()))\nt = int(input())\nfor _ in range(t):\n\tvoid = input()\n\t(ax, ay) = read()\n\t(bx, by) = read()\n\t(fx, fy) = read()\n\tans = abs(bx - ax) + abs(by - ay)\n\tif ax == bx or ay == by:\n\t\tif min(ax, bx) <= fx <= max(ax, bx) and min(ay, by) <= fy <= max(ay, by):\n\t\t\tans += 2\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\tinput()\n\t(a_x, a_y) = map(int, input().split())\n\t(b_x, b_y) = map(int, input().split())\n\t(f_x, f_y) = map(int, input().split())\n\tcount = 0\n\tcount += abs(b_x - a_x)\n\tcount += abs(b_y - a_y)\n\tif b_x == f_x == a_x and (a_y < f_y < b_y or a_y > f_y > b_y) or (b_y == f_y == a_y and (a_x < f_x < b_x or a_x > f_x > b_x)):\n\t\tcount += 2\n\tprint(count)\n", "for _ in range(int(input())):\n\tp = input()\n\t(a, b) = map(int, input().split())\n\t(x, y) = map(int, input().split())\n\t(fa, fb) = map(int, input().split())\n\tans = abs(x - a) + abs(y - b)\n\tif a == x and x == fa and (fb > min(b, y)) and (fb < max(b, y)) or (b == y and y == fb and (fa < max(a, x)) and (fa > min(a, x))):\n\t\tans += 2\n\tprint(ans)\n", "import sys, math\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\ts = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 != x2 and y1 != y2:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n\telif x1 == x2 and x2 == x3:\n\t\tif y1 < y3 and y3 < y2 or (y3 < y1 and y3 > y2):\n\t\t\tprint(abs(x1 - x2) + abs(y1 - y2) + 2)\n\t\telse:\n\t\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n\telif y1 == y2 and y2 == y3:\n\t\tif x1 < x3 and x3 < x2 or (x3 < x1 and x3 > x2):\n\t\t\tprint(abs(x1 - x2) + abs(y1 - y2) + 2)\n\t\telse:\n\t\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n\telse:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n", "for _ in range(0, int(input())):\n\tinput()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\td = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\t(n, m) = sorted([a[1], b[1]])\n\tf = a[0] == b[0] and b[0] == c[0] and (c[1] > n) and (c[1] < m)\n\t(n, m) = sorted([a[0], b[0]])\n\tf = f or (a[1] == b[1] and b[1] == c[1] and (c[0] > n) and (c[0] < m))\n\tprint(d + [0, 2][f])\n", "for _ in range(int(input())):\n\tg = input()\n\t(ax, ay) = [int(x) for x in input().split()]\n\t(bx, by) = [int(x) for x in input().split()]\n\t(fx, fy) = [int(x) for x in input().split()]\n\tif ax == bx == fx and (ay < fy < by or ay > fy > by) or (ay == by == fy and (ax < fx < bx or ax > fx > bx)):\n\t\tprint(abs(bx - ax) + abs(ay - by) + 2)\n\telse:\n\t\tprint(abs(bx - ax) + abs(ay - by))\n", "n = int(input())\nfor xx in range(n):\n\t_ = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa == xb:\n\t\tif xf == xa and (ya <= yf <= yb or yb <= yf <= ya):\n\t\t\twyn = abs(ya - yb) + 2\n\t\telse:\n\t\t\twyn = abs(ya - yb)\n\telif ya == yb:\n\t\tif yf == ya and (xa <= xf <= xb or xb <= xf <= xa):\n\t\t\twyn = abs(xa - xb) + 2\n\t\telse:\n\t\t\twyn = abs(xa - xb)\n\telse:\n\t\twyn = abs(xa - xb) + abs(ya - yb)\n\tprint(wyn)\n", "import math\nnum = int(input())\nwhile num > 0:\n\ta = input()\n\tif a == '':\n\t\ta = input().split(' ')\n\telse:\n\t\ta = a.split(' ')\n\tb = input().split(' ')\n\tc = input().split(' ')\n\ta1 = int(a[0])\n\ta2 = int(a[1])\n\tb1 = int(b[0])\n\tb2 = int(b[1])\n\tc1 = int(c[0])\n\tc2 = int(c[1])\n\tif a1 == b1 and a1 == c1:\n\t\ty = int(math.fabs(b2 - a2) + 2) if c2 < a2 and c2 > b2 or (c2 < b2 and c2 > a2) else int(math.fabs(b2 - a2))\n\t\tprint(y)\n\telif a2 == b2 and a2 == c2:\n\t\ty = int(math.fabs(b1 - a1) + 2) if c1 < a1 and c1 > b1 or (c1 < b1 and c1 > a1) else int(math.fabs(b1 - a1))\n\t\tprint(y)\n\telse:\n\t\ty = int(math.fabs(b2 - a2) + math.fabs(b1 - a1))\n\t\tprint(y)\n\tnum = num - 1\n", "def shortestpath(xa, ya, xb, yb, xf, yf):\n\tif xa == xb and ya == yb:\n\t\treturn 0\n\tif xa == xb and xa == xf:\n\t\tif ya < yb:\n\t\t\tif yf > ya and yf < yb:\n\t\t\t\treturn abs(yb - ya) + 2\n\t\t\telse:\n\t\t\t\treturn abs(yb - ya)\n\t\telif yf > yb and yf < ya:\n\t\t\treturn abs(yb - ya) + 2\n\t\telse:\n\t\t\treturn abs(yb - ya)\n\telif ya == yb and ya == yf:\n\t\tif xa > xb:\n\t\t\tif xf > xb and xf < xa:\n\t\t\t\treturn abs(xb - xa) + 2\n\t\t\telse:\n\t\t\t\treturn abs(xb - xa)\n\t\telif xf > xa and xf < xb:\n\t\t\treturn abs(xb - xa) + 2\n\t\telse:\n\t\t\treturn abs(xb - xa)\n\telse:\n\t\treturn abs(xb - xa) + abs(yb - ya)\nfor _ in range(int(input())):\n\tempty = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tprint(shortestpath(xa, ya, xb, yb, xf, yf))\n", "t = int(input())\nfor i in range(0, t):\n\tq = input()\n\t(a1, b1) = map(int, input().split())\n\t(a2, b2) = map(int, input().split())\n\t(a3, b3) = map(int, input().split())\n\tif (b1 == b3 and b1 == b2) and (a3 < a1 and a3 > a2 or (a3 > a1 and a3 < a2)):\n\t\tprint(abs(a2 - a1) + abs(b2 - b1) + 2)\n\telif (a1 == a2 and a1 == a3) and (b3 < b1 and b3 > b2 or (b3 > b1 and b3 < b2)):\n\t\tprint(abs(a2 - a1) + abs(b2 - b1) + 2)\n\telse:\n\t\tprint(abs(a2 - a1) + abs(b2 - b1))\n", "import math, sys, itertools\nwtf = sys.stdin.read()\nwtf = wtf.strip().split('\\n')\nfor t in [wtf[i:i + 4] for i in range(1, len(wtf), 4)]:\n\tA = [list(map(int, a.split())) for a in t[1:]]\n\tdy = A[1][1] - A[0][1]\n\tdx = A[1][0] - A[0][0]\n\tans = abs(dy) + abs(dx)\n\t(dxp, dyp) = (0, 0)\n\tif dy == 0 and A[0][1] == A[2][1]:\n\t\tdxp = A[0][0] - A[2][0]\n\t\tdyp = A[1][0] - A[2][0]\n\tif dx == 0 and A[0][0] == A[2][0]:\n\t\tdxp = A[0][1] - A[2][1]\n\t\tdyp = A[1][1] - A[2][1]\n\tif dxp > 0 and dyp < 0 or (dyp > 0 and dxp < 0):\n\t\tans += 2\n\tprint(ans)\n", "def main():\n\timport sys\n\tinput = sys.stdin.readline\n\tM = int(1000000000.0 + 7)\n\tfor _ in range(int(input())):\n\t\tinput()\n\t\t(xa, ya) = map(int, input().split())\n\t\t(xb, yb) = map(int, input().split())\n\t\t(xf, yf) = map(int, input().split())\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb and xb == xf:\n\t\t\tif min(ya, yb) < yf < max(ya, yb):\n\t\t\t\tans += 2\n\t\t\telse:\n\t\t\t\tans += 0\n\t\telif ya == yb and yb == yf:\n\t\t\tif min(xa, xb) < xf < max(xa, xb):\n\t\t\t\tans += 2\n\t\t\telse:\n\t\t\t\tans += 0\n\t\telse:\n\t\t\tans += 0\n\t\tprint(ans)\nmain()\n", "def proof(xm, ym, xf, yf, xs, ys):\n\tif xm == xf and xf == xs and (ys > min(ym, yf)) and (ys < max(ym, yf)):\n\t\tanz = max(ym, yf) - min(ym, yf) + 2\n\telif ym == yf and yf == ys and (xs > min(xm, xf)) and (xs < max(xm, xf)):\n\t\tanz = max(xm, xf) - min(xm, xf) + 2\n\telse:\n\t\tanz = max(ym, yf) - min(ym, yf) + (max(xm, xf) - min(xm, xf))\n\treturn anz\na = int(input())\nans = []\nfor i in range(a):\n\tz = str(input())\n\t(xm, ym) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\t(xs, ys) = map(int, input().split())\n\tans.append(proof(xm, ym, xf, yf, xs, ys))\nfor i in range(len(ans)):\n\tprint(ans[i])\n", "import math\nfor t in range(int(input())):\n\ts = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tans = abs(x1 - x2) + abs(y1 - y2)\n\tif x1 == x2 and x1 == x3 and (min(y1, y2) < y3) and (y3 < max(y1, y2)) or (y1 == y2 and y1 == y3 and (min(x1, x2) < x3) and (x3 < max(x1, x2))):\n\t\tans += 2\n\tprint(ans)\n", "def main():\n\tt = int(input())\n\twhile t > 0:\n\t\tst = input()\n\t\t(xa, ya) = map(int, input().split())\n\t\t(xb, yb) = map(int, input().split())\n\t\t(fx, fy) = map(int, input().split())\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif fx == xa and fx == xb:\n\t\t\tif fy >= min(ya, yb) and fy <= max(ya, yb):\n\t\t\t\tans = ans + 2\n\t\tif fy == yb and fy == ya:\n\t\t\tif fx >= min(xa, xb) and fx <= max(xa, xb):\n\t\t\t\tans = ans + 2\n\t\tprint(ans)\n\t\tt -= 1\nmain()\n", "import sys, math\nfrom collections import deque, defaultdict\nimport operator as op\nfrom functools import reduce\nfrom itertools import permutations\nimport heapq\nI = sys.stdin.readline\nalpha = 'abcdefghijklmnopqrstuvwxyz'\nmod = 10 ** 9 + 7\n\ndef ii():\n\treturn int(I().strip())\n\ndef li():\n\treturn list(map(int, I().strip().split()))\n\ndef mi():\n\treturn map(int, I().strip().split())\n\ndef ncr(n, r):\n\tr = min(r, n - r)\n\tnumer = reduce(op.mul, range(n, n - r, -1), 1)\n\tdenom = reduce(op.mul, range(1, r + 1), 1)\n\treturn numer // denom\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\telif n <= 2:\n\t\treturn True\n\telse:\n\t\tfor i in range(2, int(n ** 0.5) + 1):\n\t\t\tif n % i == 0:\n\t\t\t\treturn False\n\t\treturn True\n\ndef main():\n\tans = ''\n\tfor _ in range(ii()):\n\t\tI()\n\t\t(xa, ya) = mi()\n\t\t(xb, yb) = mi()\n\t\t(xf, yf) = mi()\n\t\tcnt = 0\n\t\tif xa == xb:\n\t\t\tcnt = abs(yb - ya)\n\t\t\tif xf == xa and (yf > min(ya, yb) and yf < max(ya, yb)):\n\t\t\t\tcnt += 2\n\t\telif ya == yb:\n\t\t\tcnt = abs(xa - xb)\n\t\t\tif yf == ya and (xf > min(xa, xb) and xf < max(xa, xb)):\n\t\t\t\tcnt += 2\n\t\telse:\n\t\t\tcnt = abs(yb - ya) + abs(xa - xb)\n\t\tans += str(cnt) + '\\n'\n\tprint(ans)\nmain()\n", "import sys\npin = sys.stdin.readline\nT = int(pin())\npin()\nfor t in range(T):\n\tA = [*map(int, pin().split())]\n\tB = [*map(int, pin().split())]\n\tF = [*map(int, pin().split())]\n\tpin()\n\tans = abs(A[0] - B[0]) + abs(A[1] - B[1])\n\tif A[0] == B[0] == F[0] and (A[1] <= F[1] <= B[1] or A[1] >= F[1] >= B[1]):\n\t\tans += 2\n\tif A[1] == B[1] == F[1] and (A[0] <= F[0] <= B[0] or A[0] >= F[0] >= B[0]):\n\t\tans += 2\n\tprint(ans)\n", "t = int(input())\nwhile t != 0:\n\ta = input()\n\t(x, y) = map(int, input().split())\n\t(x1, y1) = map(int, input().split())\n\t(f, f1) = map(int, input().split())\n\tif x == x1:\n\t\tmaxi = max(y, y1)\n\t\tmini = min(y, y1)\n\t\tres = maxi - mini\n\t\tif mini < f1 < maxi and f == x:\n\t\t\tres += 2\n\t\tprint(res)\n\telif y == y1:\n\t\tmaxi = max(x, x1)\n\t\tmini = min(x, x1)\n\t\tres = maxi - mini\n\t\tif mini < f < maxi and f1 == y:\n\t\t\tres += 2\n\t\tprint(res)\n\telse:\n\t\tn = abs(x - x1)\n\t\tm = abs(y - y1)\n\t\tres = n + m\n\t\tprint(res)\n\tt -= 1\n", "for _ in range(int(input())):\n\ta = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(f1, f2) = map(int, input().split())\n\tif x1 != x2 and y1 != y2:\n\t\tprint(abs(x2 - x1) + abs(y2 - y1))\n\t\tcontinue\n\tif x1 == x2:\n\t\tif f1 != x1:\n\t\t\tprint(abs(y2 - y1))\n\t\t\tcontinue\n\t\telse:\n\t\t\tif f2 > min(y1, y2) and f2 < max(y1, y2):\n\t\t\t\tprint(abs(y2 - y1) + 2)\n\t\t\telse:\n\t\t\t\tprint(abs(y2 - y1))\n\t\t\tcontinue\n\tif y1 == y2:\n\t\tif f2 != y1:\n\t\t\tprint(abs(x1 - x2))\n\t\t\tcontinue\n\t\telif f1 > min(x1, x2) and f1 < max(x2, x1):\n\t\t\tprint(abs(x1 - x2) + 2)\n\t\telse:\n\t\t\tprint(abs(x2 - x1))\n", "from sys import stdin\n\ndef main():\n\tcases = int(stdin.readline().strip())\n\tfor i in range(cases):\n\t\tblank = stdin.readline()\n\t\t(Ax, Ay) = map(int, stdin.readline().split())\n\t\t(Bx, By) = map(int, stdin.readline().split())\n\t\t(Fx, Fy) = map(int, stdin.readline().split())\n\t\tans = 0\n\t\tif (Ax == Bx and Bx == Fx) and min(Ay, By) < Fy < max(Ay, By):\n\t\t\tans = abs(Ax - Bx) + abs(Ay - By) + 2\n\t\telif (Ay == By and By == Fy) and min(Ax, Bx) < Fx < max(Ax, Bx):\n\t\t\tans = abs(Ax - Bx) + abs(Ay - By) + 2\n\t\telse:\n\t\t\tans = abs(Ax - Bx) + abs(Ay - By)\n\t\tprint(ans)\nmain()\n", "for _ in range(int(input())):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 == x2 == x3:\n\t\tif y1 < y3 < y2 or y2 < y3 < y1:\n\t\t\tprint(abs(y1 - y2) + 2)\n\t\telse:\n\t\t\tprint(abs(y1 - y2))\n\telif y1 == y2 == y3:\n\t\tif x1 < x3 < x2 or x2 < x3 < x1:\n\t\t\tprint(abs(x1 - x2) + 2)\n\t\telse:\n\t\t\tprint(abs(x1 - x2))\n\telse:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n", "for z in range(int(input())):\n\tp = input()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\tif ax == bx == fx and (ay < fy < by or by < fy < ay) or (ay == by == fy and (ax < fx < bx or bx < fx < ax)):\n\t\tif ay == by:\n\t\t\tprint(abs(bx - ax) + 2)\n\t\telse:\n\t\t\tprint(abs(by - ay) + 2)\n\telse:\n\t\tprint(abs(by - ay) + abs(bx - ax))\n", "def solve():\n\tt = int(input())\n\tpaths = []\n\tfor i in range(t):\n\t\tinput()\n\t\ta = list(map(int, input().split(' ')))\n\t\tb = list(map(int, input().split(' ')))\n\t\tf = list(map(int, input().split(' ')))\n\t\tif a[0] == f[0] and a[0] == b[0]:\n\t\t\tif f[1] < max(a[1], b[1]) and f[1] > min(a[1], b[1]):\n\t\t\t\tpaths.append(abs(a[1] - b[1]) + 2)\n\t\t\telse:\n\t\t\t\tpaths.append(abs(a[1] - b[1]))\n\t\telif a[1] == f[1] and a[1] == b[1]:\n\t\t\tif f[0] < max(a[0], b[0]) and f[0] > min(a[0], b[0]):\n\t\t\t\tpaths.append(abs(a[0] - b[0]) + 2)\n\t\t\telse:\n\t\t\t\tpaths.append(abs(a[0] - b[0]))\n\t\telse:\n\t\t\tpaths.append(abs(a[0] - b[0]) + abs(a[1] - b[1]))\n\tprint('\\n')\n\tfor i in paths:\n\t\tprint(i)\nsolve()\n", "for _ in range(int(input())):\n\tres = input()\n\t(n1, m1) = map(int, input().split())\n\t(n2, m2) = map(int, input().split())\n\t(x, y) = map(int, input().split())\n\tans = 0\n\tif n1 == n2 and n1 == x:\n\t\tif m1 <= y and y <= m2 or (m2 <= y and y <= m1):\n\t\t\tans = abs(n1 - n2) + abs(m2 - m1) + 2\n\t\telse:\n\t\t\tans = abs(n1 - n2) + abs(m2 - m1)\n\telif m1 == m2 and m1 == y:\n\t\tif n1 <= x and x <= n2 or (n2 <= x and x <= n1):\n\t\t\tans = abs(n1 - n2) + abs(m2 - m1) + 2\n\t\telse:\n\t\t\tans = abs(n1 - n2) + abs(m2 - m1)\n\telse:\n\t\tans = abs(n1 - n2) + abs(m2 - m1)\n\tprint(ans)\n", "from sys import stdin, stdout\nfrom io import StringIO\n\ndef between(x1, x2, x3):\n\treturn x1 < x2 < x3 or x1 > x2 > x3\n\ndef linear_between(u, v, w):\n\treturn u[0] == v[0] == w[0] and between(u[1], v[1], w[1]) or (u[1] == v[1] == w[1] and between(u[0], v[0], w[0]))\n\ndef main(inbuf, outbuf):\n\tt = int(inbuf.readline())\n\tfor _ in range(t):\n\t\t_ = inbuf.readline()\n\t\ta = tuple(map(int, inbuf.readline().split()))\n\t\tb = tuple(map(int, inbuf.readline().split()))\n\t\tf = tuple(map(int, inbuf.readline().split()))\n\t\tcorrection = 2 if linear_between(a, f, b) else 0\n\t\tdist = abs(a[0] - b[0]) + abs(a[1] - b[1]) + correction\n\t\tprint(str(dist), file=outbuf, end='\\n')\noutbuf = StringIO()\nmain(stdin, outbuf)\nprint(outbuf.getvalue(), file=stdout)\n", "for i in range(int(input())):\n\ta = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tans = abs(x1 - x2) + abs(y1 - y2)\n\tif y1 == y2 and y2 == y3 and (x3 > min(x1, x2)) and (x3 < max(x1, x2)) or (x1 == x2 and x2 == x3 and (y3 > min(y1, y2)) and (y3 < max(y1, y2))):\n\t\tans += 2\n\tprint(ans)\n", "from sys import *\nfrom math import *\nfrom collections import *\nimport string\nimport re\nfrom bisect import *\nfrom functools import reduce\nfrom itertools import permutations, combinations\nt = stdin.readline\nR = range\np = stdout.write\nmod = int(1000000000.0) + 7\nMAX = 9223372036854775808\nINF = float('inf')\nlower = string.ascii_lowercase\nupper = string.ascii_uppercase\nnumbers = string.digits\nS = lambda : t().strip()\nI = lambda : int(t())\nGI = lambda : map(int, input().strip().split())\nGS = lambda : map(str, t().strip().split())\nIL = lambda : list(map(int, t().strip().split()))\nSL = lambda : list(map(str, t().strip().split()))\nmat = lambda n: [IL() for i in range(n)]\nd2b = lambda n: bin(n)[2:]\nispow2 = lambda x: x != 0 and x & x - 1 == 0\npowof2 = lambda x: 1 << x\niSq = lambda x: ceil(float(sqrt(x))) == floor(float(sqrt(x)))\n\ndef sieve(n):\n\treturn reduce(lambda r, x: r - set(range(x ** 2, n, x)) if x in r else r, range(2, int(n ** 0.5) + 1), set(range(2, n)))\n\ndef ls(x, y):\n\treturn x << y\n\ndef rs(x, y):\n\treturn x << y\n\ndef BS_left(n, a, x):\n\ti = bisect_left(a, x)\n\treturn [-1, i][i != n and a[i] == x]\n\ndef BS_right(n, a, x):\n\ti = bisect_right(a, x)\n\treturn [-1, i][i != n and a[i] == x]\nfor _ in range(I()):\n\tt()\n\t(xa, ya) = GI()\n\t(xb, yb) = GI()\n\t(xf, yf) = GI()\n\tans = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb == xf and (ya < yf < yb or ya > yf > yb) or (ya == yb == yf and (xa < xf < xb or xa > xf > xb)):\n\t\tans += 2\n\tprint(ans)\n", "for _ in range(int(input())):\n\ts = input()\n\t(a, b) = map(int, input().split())\n\t(c, d) = map(int, input().split())\n\t(x, y) = map(int, input().split())\n\tgen = abs(d - b) + abs(c - a)\n\tif min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):\n\t\tif a == c == x:\n\t\t\tprint(gen + 2)\n\t\telif b == d == y:\n\t\t\tprint(gen + 2)\n\t\telse:\n\t\t\tprint(gen)\n\telse:\n\t\tprint(gen)\n", "import sys\nimport math\n\ndef read_int():\n\treturn int(sys.stdin.readline())\n\ndef read_ints():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef write(x):\n\tsys.stdout.write(x + '\\n')\nfor i in range(int(input())):\n\tb = input()\n\t(xa, ya) = read_ints()\n\t(xb, yb) = read_ints()\n\t(xf, yf) = read_ints()\n\tans = abs(xa - xb) + abs(ya - yb)\n\tif xa == xf == xb and min(ya, yb) < yf < max(ya, yb) or (ya == yf == yb and min(xa, xb) < xf < max(xa, xb)):\n\t\tans += 2\n\twrite(str(ans))\n", "import sys\nfrom sys import stdin, stdout\nfrom math import ceil, floor, sqrt, log, log2, log10\nfrom collections import Counter\nint_max = float('inf')\nint_min = -float('inf')\nANS = []\ninput = stdin.readline\n\ndef solve():\n\tpass\nt = int(input())\nfor i in range(t):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xo, yo) = map(int, input().split())\n\tif xa == xb == xo and (ya >= yo >= yb or ya <= yo <= yb):\n\t\tprint(abs(xa - xb) + abs(ya - yb) + 2)\n\t\tcontinue\n\tif ya == yb == yo and (xa >= xo >= xb or xa <= xo <= xb):\n\t\tprint(abs(xa - xb) + abs(ya - yb) + 2)\n\t\tcontinue\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\tcontinue\nprint('\\n'.join(ANS))\n", "t = int(input())\nli = []\nfor i in range(t):\n\tn = input()\n\t(xa, xb) = map(int, input().split())\n\t(ya, yb) = map(int, input().split())\n\t(fa, fb) = map(int, input().split())\n\tans = abs(xa - ya) + abs(xb - yb)\n\tif xa == ya and xa == fa and (xb > fb and yb < fb or (xb < fb and yb > fb)):\n\t\tans += 2\n\telif xb == yb and xb == fb and (xa > fa and ya < fa or (xa < fa and ya > fa)):\n\t\tans += 2\n\tli.append(ans)\nfor i in range(len(li)):\n\tprint(li[i])\n", "t = int(input())\nfor i in range(t):\n\tn = input()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(tx, ty) = map(int, input().split())\n\tif ax != bx and ay != by:\n\t\tprint(max(ax, bx) - min(ax, bx) + max(ay, by) - min(ay, by))\n\telif ax == bx:\n\t\tif tx == ax and min(ay, by) < ty < max(ay, by):\n\t\t\tprint(max(ay, by) - min(ay, by) + 2)\n\t\telse:\n\t\t\tprint(max(ay, by) - min(ay, by))\n\telif ty == ay and min(ax, bx) < tx < max(ax, bx):\n\t\tprint(max(ax, bx) - min(ax, bx) + 2)\n\telse:\n\t\tprint(max(ax, bx) - min(ax, bx))\n", "t = int(input())\nfor _ in range(t * 2):\n\tif _ % 2 == 1:\n\t\t(ax, ay) = [int(x) for x in input().split()]\n\t\t(bx, by) = [int(x) for x in input().split()]\n\t\t(fx, fy) = [int(x) for x in input().split()]\n\t\tif ax == bx == fx and min(ay, by) < fy < max(ay, by):\n\t\t\tprint(abs(ax - bx) + abs(ay - by) + 2)\n\t\telif ay == by == fy and min(ax, bx) < fx < max(ax, bx):\n\t\t\tprint(abs(ax - bx) + abs(ay - by) + 2)\n\t\telse:\n\t\t\tprint(abs(ax - bx) + abs(ay - by))\n\telse:\n\t\ta = input()\n", "ans = []\nfor _ in range(int(input())):\n\tinput()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\tdist = abs(bx - ax) + abs(by - ay)\n\tif ay == by and ay == fy and (fx > ax and fx < bx or (fx > bx and fx < ax)):\n\t\tdist += 2\n\tif ax == bx and ax == fx and (fy > ay and fy < by or (fy > by and fy < ay)):\n\t\tdist += 2\n\tans.append(dist)\nfor i in ans:\n\tprint(i)\n", "test_cases = int(input())\n_ = input()\ntests = []\nfor _ in range(test_cases - 1):\n\ta_cord = list(map(lambda x: int(x), input().split()))\n\tb_cord = list(map(lambda x: int(x), input().split()))\n\tf_cord = list(map(lambda x: int(x), input().split()))\n\tignore = input()\n\ttemp = [a_cord, b_cord, f_cord]\n\ttests.append(temp)\nif test_cases != 1:\n\ta_cord = list(map(lambda x: int(x), input().split()))\n\tb_cord = list(map(lambda x: int(x), input().split()))\n\tf_cord = list(map(lambda x: int(x), input().split()))\n\ttemp = [a_cord, b_cord, f_cord]\n\ttests.append(temp)\nfor test in tests:\n\ta_cord = test[0]\n\tb_cord = test[1]\n\tf_cord = test[2]\n\tdist = 0\n\tdist += abs(b_cord[0] - a_cord[0])\n\tdist += abs(b_cord[1] - a_cord[1])\n\tif f_cord[0] == a_cord[0] and f_cord[0] == b_cord[0] or (f_cord[1] == b_cord[1] and f_cord[1] == a_cord[1]):\n\t\tif f_cord[0] > a_cord[0] and f_cord[0] > b_cord[0] or (f_cord[1] > a_cord[1] and f_cord[1] > b_cord[1]) or (f_cord[0] < a_cord[0] and f_cord[0] < b_cord[0]) or (f_cord[1] < a_cord[1] and f_cord[1] < b_cord[1]):\n\t\t\tdist -= 2\n\t\tdist += 2\n\tprint(dist)\n", "def finddistance(xA, yA, xB, yB, xF, yF):\n\tif xA > xB:\n\t\t(xA, xB) = (xB, xA)\n\tif yA > yB:\n\t\t(yA, yB) = (yB, yA)\n\tif xA == xB == xF and yA < yF < yB or (yA == yB == yF and xA < xF < xB):\n\t\treturn abs(xA - xB) + abs(yA - yB) + 2\n\treturn abs(xA - xB) + abs(yA - yB)\nt = int(input())\nfor i in range(t):\n\tinput()\n\t(xA, yA) = map(int, input().split())\n\t(xB, yB) = map(int, input().split())\n\t(xF, yF) = map(int, input().split())\n\tprint(finddistance(xA, yA, xB, yB, xF, yF))\n", "def find_shortest_path_len(xA, yA, xB, yB, xF, yF):\n\tair_path = abs(xA - xB) + abs(yA - yB)\n\tc = 0\n\tif xA == xB == xF:\n\t\tif yA < yF < yB or yB < yF < yA:\n\t\t\tc = 2\n\tif yA == yB == yF:\n\t\tif xA < xF < xB or xB < xF < xA:\n\t\t\tc = 2\n\treturn air_path + c\nimport sys\nT = int(input())\nwhile T:\n\tsys.stdin.readline()\n\t(xA, yA) = list(map(int, sys.stdin.readline().split()))\n\t(xB, yB) = list(map(int, sys.stdin.readline().split()))\n\t(xF, yF) = list(map(int, sys.stdin.readline().split()))\n\tprint(find_shortest_path_len(xA, yA, xB, yB, xF, yF))\n\tT -= 1\n", "f = filter(str.strip, open(0))\nR = lambda : map(int, next(f).split())\n(t,) = R()\nwhile t:\n\tt -= 1\n\t((k, (u, v, w)), (m, (x, y, z))) = sorted(((len({*x}), x) for x in zip(R(), R(), R())))\n\tprint(abs(u - v) + abs(x - y) + 2 * (k < 2 and (x - z) * (y - z) < 0))\n", "def getlist():\n\treturn list(map(int, input().split()))\n\ndef main():\n\tt = int(input())\n\tfor num in range(t):\n\t\ttemp = input()\n\t\t(x, y) = map(int, input().split())\n\t\t(m, n) = map(int, input().split())\n\t\t(a, b) = map(int, input().split())\n\t\tif x == m:\n\t\t\tif a == m and b in range(min(y, n), max(y, n)):\n\t\t\t\tlength = abs(y - n) + 2\n\t\t\telse:\n\t\t\t\tlength = abs(y - n)\n\t\telif y == n:\n\t\t\tif b == n and a in range(min(x, m), max(x, m)):\n\t\t\t\tlength = abs(x - m) + 2\n\t\t\telse:\n\t\t\t\tlength = abs(x - m)\n\t\telse:\n\t\t\tlength = abs(x - m) + abs(y - n)\n\t\tprint(length)\nmain()\n", "import sys\nfrom collections import deque\ninput = sys.stdin.readline\nt = int(input())\nresults = []\nwhile t > 0:\n\ttemp = input()\n\tt -= 1\n\t(A1, A2) = map(int, input().rstrip().split())\n\t(B1, B2) = map(int, input().rstrip().split())\n\t(F1, F2) = map(int, input().rstrip().split())\n\ta = (A1, A2)\n\tb = (B1, B2)\n\tf = (F1, F2)\n\tif A1 == B1 and B1 == F1:\n\t\tif min(A2, B2) <= F2 and F2 <= max(A2, B2):\n\t\t\tresults.append(abs(B2 - A2) + 2)\n\t\telse:\n\t\t\tresults.append(abs(B2 - A2))\n\telif A2 == B2 and B2 == F2:\n\t\tif min(A1, B1) <= F1 and F1 <= max(A1, B1):\n\t\t\tresults.append(abs(B1 - A1) + 2)\n\t\telse:\n\t\t\tresults.append(abs(B1 - A1))\n\telse:\n\t\tresults.append(abs(B1 - A1) + abs(B2 - A2))\nfor i in results:\n\tprint(i)\n", "t = int(input())\nfor i in range(t):\n\tinput()\n\t(ax, ay) = list(map(int, input().split()))\n\t(bx, by) = list(map(int, input().split()))\n\t(fx, fy) = list(map(int, input().split()))\n\tif ax != bx and ay != by:\n\t\tprint(abs(bx - ax) + abs(by - ay))\n\telif fx > ax and fx < bx and (ay == by == fy) or (fx > bx and fx < ax and (ay == by == fy)) or (fy > ay and fy < by and (ax == bx == fx)) or (fy > by and fy < ay and (ax == bx == fx)):\n\t\tprint(abs(bx - ax) + abs(by - ay) + 2)\n\telse:\n\t\tprint(abs(bx - ax) + abs(by - ay))\n", "def main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tinput()\n\t\t(xa, ya) = map(int, input().split())\n\t\t(xb, yb) = map(int, input().split())\n\t\t(xf, yf) = map(int, input().split())\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb and xa == xf and (min(ya, yb) < yf < max(ya, yb)) or (ya == yb and ya == yf and (min(xa, xb) < xf < max(xa, xb))):\n\t\t\tans += 2\n\t\tprint(ans)\nmain()\n", "import math\nimport collections\nfrom sys import stdin, stdout, setrecursionlimit\nfrom bisect import bisect_left as bsl\nfrom bisect import bisect_right as bsr\nimport heapq as hq\nsetrecursionlimit(2 ** 20)\nt = 1\nt = int(stdin.readline())\nfor _ in range(t):\n\ta = stdin.readline()\n\t(xa, ya) = list(map(int, stdin.readline().rstrip().split()))\n\t(xb, yb) = list(map(int, stdin.readline().rstrip().split()))\n\t(xf, yf) = list(map(int, stdin.readline().rstrip().split()))\n\tif xa != xb and ya != yb:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n\telse:\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb and ya == yb:\n\t\t\tprint(0)\n\t\telse:\n\t\t\tif xa == xb and xa == xf and (yf > min(ya, yb)) and (yf < max(ya, yb)) or ((ya == yb and ya == yf) and xf > min(xa, xb) and (xf < max(xa, xb))):\n\t\t\t\tans += 2\n\t\t\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\tignore_space = input()\n\t(xa, ya) = input().split()\n\t(xb, yb) = input().split()\n\t(xf, yf) = input().split()\n\txa = int(xa)\n\tya = int(ya)\n\txb = int(xb)\n\tyb = int(yb)\n\txf = int(xf)\n\tyf = int(yf)\n\tif xa == xb:\n\t\tif xa == xf:\n\t\t\tif yb < yf < ya or yb > yf > ya:\n\t\t\t\tprint(abs(xa - xb) + abs(ya - yb) + 2)\n\t\t\telse:\n\t\t\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\telse:\n\t\t\tprint(abs(xa - xb) + abs(ya - yb))\n\telif ya == yb:\n\t\tif ya == yf:\n\t\t\tif xb < xf < xa or xb > xf > xa:\n\t\t\t\tprint(abs(xa - xb) + abs(ya - yb) + 2)\n\t\t\telse:\n\t\t\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\telse:\n\t\t\tprint(abs(xa - xb) + abs(ya - yb))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "t = int(input())\nfor i in range(t):\n\te = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 == x2 and x2 == x3 and (min(y1, y2) < y3 < max(y1, y2)) or (y1 == y2 and y2 == y3 and (min(x1, x2) < x3 < max(x1, x2))):\n\t\tprint(abs(x1 - x2) + abs(y1 - y2) + 2)\n\telse:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor i in range(t):\n\tline = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tans = abs(x1 - x2) + abs(y1 - y2)\n\tif x1 == x2 and x2 == x3:\n\t\tif y1 < y3 < y2 or y2 < y3 < y1:\n\t\t\tans += 2\n\telif y1 == y2 and y2 == y3:\n\t\tif x1 < x3 < x2 or x2 < x3 < x1:\n\t\t\tans += 2\n\tprint(ans)\n", "for i in range(int(input())):\n\tn = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\trxab = abs(xb - xa)\n\tryab = abs(yb - ya)\n\trxaf = abs(xf - xa)\n\tryaf = abs(yf - ya)\n\trxfb = abs(xb - xf)\n\tryfb = abs(yb - yf)\n\tif ya == yb == yf and rxab == rxaf + rxfb or (xa == xb == xf and ryab == ryaf + ryfb):\n\t\tr = 2\n\telse:\n\t\tr = 0\n\tr += rxab + ryab\n\tprint(r)\n", "import sys\ninput = sys.stdin.readline\noutput = sys.stdout.write\n\ndef main():\n\ttests = int(input().rstrip())\n\tfor i in range(tests):\n\t\tinput()\n\t\t(xa, ya) = map(int, input().rstrip().split())\n\t\t(xb, yb) = map(int, input().rstrip().split())\n\t\t(xf, yf) = map(int, input().rstrip().split())\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb == xf:\n\t\t\tif ya < yf < yb or yb < yf < ya:\n\t\t\t\tans += 2\n\t\telif ya == yb == yf:\n\t\t\tif xa < xf < xb or xb < xf < xa:\n\t\t\t\tans += 2\n\t\toutput(str(ans))\n\t\toutput('\\n')\nmain()\n", "for f in range(int(input())):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tres = abs(xa - xb) + abs(ya - yb)\n\tif xf == xa == xb and min(ya, yb) < yf < max(ya, yb):\n\t\tres += 2\n\telif yf == ya == yb and min(xa, xb) < xf < max(xa, xb):\n\t\tres += 2\n\tprint(res)\n", "for _ in range(int(input())):\n\tinput()\n\t(xA, yA) = map(int, input().split())\n\t(xB, yB) = map(int, input().split())\n\t(xF, yF) = map(int, input().split())\n\tif xA == xB == xF and min(yA, yB) < yF < max(yA, yB) or (yA == yB == yF and min(xA, xB) < xF < max(xA, xB)):\n\t\tprint(abs(xA - xB) + abs(yA - yB) + 2)\n\telse:\n\t\tprint(abs(xA - xB) + abs(yA - yB))\n", "import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef main(t):\n\ts = input()\n\t(a1, a2) = map(int, input().split())\n\t(b1, b2) = map(int, input().split())\n\t(f1, f2) = map(int, input().split())\n\tans = abs(b1 - a1) + abs(b2 - a2)\n\tif a2 == b2 and b2 == f2 and (a1 < f1 < b1 or b1 < f1 < a1):\n\t\tans += 2\n\telif a1 == b1 and b1 == f1 and (a2 < f2 < b2 or b2 < f2 < a2):\n\t\tans += 2\n\tprint(ans)\nT = int(input())\nt = 1\nwhile t <= T:\n\tmain(t)\n\tt += 1\n", "t = 0\nt = int(input())\nshortest_dist = []\nfor i in range(t):\n\tinput()\n\t(a_x, a_y) = map(int, input().split())\n\t(b_x, b_y) = map(int, input().split())\n\t(t_x, t_y) = map(int, input().split())\n\tshortest = int(abs(a_x - b_x)) + int(abs(a_y - b_y))\n\tif a_x == b_x and a_x == t_x or (a_y == b_y and a_y == t_y):\n\t\tif a_y == b_y:\n\t\t\t(min_x, max_x) = (a_x, b_x) if a_x <= b_x else (b_x, a_x)\n\t\t\tif min_x < t_x < max_x:\n\t\t\t\tshortest += 2\n\t\telif a_x == b_x:\n\t\t\t(min_y, max_y) = (a_y, b_y) if a_y <= b_y else (b_y, a_y)\n\t\t\tif min_y < t_y < max_y:\n\t\t\t\tshortest += 2\n\tshortest_dist.append(shortest)\nfor i in range(t):\n\tprint(shortest_dist[i])\n", "class coordinates:\n\n\tdef __init__(self, x, y):\n\t\tself.x = x\n\t\tself.y = y\n\n\tdef get_x(self):\n\t\treturn self.x\n\n\tdef get_y(self):\n\t\treturn self.y\nn = int(input())\na = []\nb = []\nf = []\nfor i in range(n):\n\tinput()\n\t(x, y) = input().split(' ')\n\ta.append(coordinates(int(x), int(y)))\n\t(x, y) = input().split(' ')\n\tb.append(coordinates(int(x), int(y)))\n\t(x, y) = input().split(' ')\n\tf.append(coordinates(int(x), int(y)))\nfor i in range(n):\n\tresult = abs(a[i].get_x() - b[i].get_x()) + abs(a[i].get_y() - b[i].get_y())\n\tif a[i].get_x() == b[i].get_x() and a[i].get_x() == f[i].get_x():\n\t\tif f[i].get_y() < a[i].get_y() and f[i].get_y() < b[i].get_y() or (f[i].get_y() > a[i].get_y() and f[i].get_y() > b[i].get_y()):\n\t\t\tpass\n\t\telse:\n\t\t\tresult += 2\n\tif a[i].get_y() == b[i].get_y() and a[i].get_y() == f[i].get_y():\n\t\tif f[i].get_x() < a[i].get_x() and f[i].get_x() < b[i].get_x() or (f[i].get_x() > a[i].get_x() and f[i].get_x() > b[i].get_x()):\n\t\t\tpass\n\t\telse:\n\t\t\tresult += 2\n\tprint(result)\n", "import sys\ninput = sys.stdin.readline\nsys.setrecursionlimit(3 * 10 ** 5)\n\ndef inp():\n\treturn int(input())\n\ndef st():\n\treturn input().rstrip('\\n')\n\ndef lis():\n\treturn list(map(int, input().split()))\n\ndef ma():\n\treturn map(int, input().split())\nt = inp()\nwhile t:\n\tt -= 1\n\ts = st()\n\t(ax, ay) = ma()\n\t(bx, by) = ma()\n\t(fx, fy) = ma()\n\tz = abs(ax - bx) + abs(by - ay)\n\tif ay == by and fy == ay:\n\t\tif fx >= min(ax, bx) and fx <= max(ax, bx):\n\t\t\tz += 2\n\tif bx == ax and ax == fx:\n\t\tif fy >= min(ay, by) and fy <= max(by, ay):\n\t\t\tz += 2\n\tprint(z)\n", "def solve():\n\t(a1, a2) = map(int, input().split())\n\t(b1, b2) = map(int, input().split())\n\t(c1, c2) = map(int, input().split())\n\tif a1 == b1 and b1 == c1:\n\t\tif a2 < c2 and c2 < b2 or (b2 < c2 and c2 < a2):\n\t\t\tprint(abs(a2 - b2) + 2)\n\t\t\treturn\n\t\telse:\n\t\t\tprint(abs(a2 - b2))\n\t\t\treturn\n\tif a2 == b2 and b2 == c2:\n\t\tif a1 < c1 and c1 < b1 or (b1 < c1 and c1 < a1):\n\t\t\tprint(abs(a1 - b1) + 2)\n\t\t\treturn\n\t\telse:\n\t\t\tprint(abs(a1 - b1))\n\t\t\treturn\n\tans = abs(a1 - b1) + abs(a2 - b2)\n\tprint(ans)\nfor testis in range(int(input())):\n\tx = input()\n\tsolve()\n", "t = int(input())\nfor i in range(t):\n\tn = input()\n\t(a, b) = [int(j) for j in input().split()]\n\t(c, d) = [int(j) for j in input().split()]\n\t(e, f) = [int(j) for j in input().split()]\n\tpath = abs(a - c) + abs(b - d) + 2 * ((a == c == e) * (b - f) * (d - f) | (b == d == f) * (a - e) * (c - e) < 0)\n\tprint(path)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\temp = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tans = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb and xa == xf and (yf > min(ya, yb)) and (yf < max(ya, yb)):\n\t\tans += 2\n\tif ya == yb and yb == yf and (xf > min(xa, xb)) and (xf < max(xa, xb)):\n\t\tans += 2\n\tsys.stdout.write(str(ans) + '\\n')\n", "import math\nt = int(input())\nfor i in range(t):\n\tk = input()\n\t(xa, ya) = list(map(int, input().split()))\n\t(xb, yb) = list(map(int, input().split()))\n\t(xf, yf) = list(map(int, input().split()))\n\tif xa == xb == xf:\n\t\tif yf > min(ya, yb) and yf < max(ya, yb):\n\t\t\tprint(abs(ya - yb) + 2)\n\t\telse:\n\t\t\tprint(abs(ya - yb))\n\telif ya == yb == yf:\n\t\tif xf > min(xa, xb) and xf < max(xa, xb):\n\t\t\tprint(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tprint(abs(xa - xb))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "t = int(input())\ninput()\nfor i in range(t):\n\ta = [int(j) for j in input().split(' ')]\n\tb = [int(j) for j in input().split(' ')]\n\tc = [int(j) for j in input().split(' ')]\n\te = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\tif a[0] == b[0] and a[0] == c[0] and (a[1] < c[1] < b[1] or b[1] < c[1] < a[1]):\n\t\te += 2\n\tif a[1] == b[1] and a[1] == c[1] and (a[0] < c[0] < b[0] or b[0] < c[0] < a[0]):\n\t\te += 2\n\tprint(e)\n\tif i < t - 1:\n\t\tinput()\n", "for _ in range(int(input())):\n\tarr = []\n\tinput()\n\tfor i in range(3):\n\t\tarr.append(list(map(int, input().split())))\n\t(x1, y1) = arr[0]\n\t(x2, y2) = arr[1]\n\t(x3, y3) = arr[2]\n\tans = abs(x2 - x1) + abs(y1 - y2)\n\tif x1 == x2 == x3 and (y1 < y3 < y2 or y2 < y3 < y1) or (y1 == y2 == y3 and (x1 < x3 < x2 or x2 < x3 < x1)):\n\t\tans += 2\n\tprint(ans)\n", "def s(x1, y1, x2, y2, x3, y3):\n\tif x1 == x2 == x3:\n\t\tif y1 < y3 < y2 or y2 < y3 < y1:\n\t\t\treturn abs(y1 - y2) + 2\n\t\telse:\n\t\t\treturn abs(y1 - y2)\n\telif y1 == y2 == y3:\n\t\tif x1 < x3 < x2 or x2 < x3 < x1:\n\t\t\treturn abs(x1 - x2) + 2\n\t\telse:\n\t\t\treturn abs(x1 - x2)\n\telse:\n\t\treturn abs(x1 - x2) + abs(y1 - y2)\na = int(input())\nfor _ in range(a):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tprint(s(x1, y1, x2, y2, x3, y3))\n", "tc = int(input())\ninput()\nwhile tc:\n\ttc -= 1\n\t(a, b, f) = (list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split())))\n\tif tc:\n\t\tinput()\n\textra = 0\n\tif a[0] == b[0] == f[0] and min(a[1], b[1]) < f[1] < max(a[1], b[1]) or (a[1] == b[1] == f[1] and min(a[0], b[0]) < f[0] < max(a[0], b[0])):\n\t\textra = 2\n\tprint(extra + abs(b[1] - a[1]) + abs(b[0] - a[0]))\n", "import math\n\ndef ex_9_calculating(data):\n\t(a, b, f) = data\n\tif a[0] != b[0] and a[1] != b[1]:\n\t\tsteps = math.fabs(a[0] - b[0]) + math.fabs(a[1] - b[1])\n\tif a[0] == b[0]:\n\t\tif f[0] != a[0]:\n\t\t\tsteps = math.fabs(a[1] - b[1])\n\t\telif f[0] == a[0] and f[1] in range(min(a[1], b[1]), max(a[1], b[1])):\n\t\t\tsteps = math.fabs(a[1] - b[1]) + 2\n\t\telse:\n\t\t\tsteps = math.fabs(a[1] - b[1])\n\telif a[1] == b[1]:\n\t\tif f[1] != a[1]:\n\t\t\tsteps = math.fabs(a[0] - b[0])\n\t\telif f[1] == a[1] and f[0] in range(min(a[0], b[0]), max(a[0], b[0])):\n\t\t\tsteps = math.fabs(a[0] - b[0]) + 2\n\t\telse:\n\t\t\tsteps = math.fabs(a[0] - b[0])\n\treturn int(steps)\ntests = int(input())\ndata = {}\nfor i in range(tests):\n\tdata[i] = []\n\tfor j in range(4):\n\t\tdata[i].append([int(x) for x in input().split()])\n\tdata[i].pop(0)\nfor key in data.keys():\n\tprint(ex_9_calculating(data[key]))\n", "t = int(input())\nwhile t > 0:\n\tcoor = []\n\tinput()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\t(h, k) = sorted([ax, bx])\n\t(i, j) = sorted([ay, by])\n\td = abs(ax - bx) + abs(ay - by)\n\tif ax == bx or ay == by:\n\t\tif fx == ax or fy == ay:\n\t\t\tif (fx < ax and fx > bx or (fx > ax and fx < bx)) or (fy > ay and fy < by or (fy < ay and fy > by)):\n\t\t\t\tprint(d + 2)\n\t\t\telse:\n\t\t\t\tprint(d)\n\t\telse:\n\t\t\tprint(d)\n\telse:\n\t\tprint(d)\n\tt -= 1\n", "from sys import stdin\nt = int(stdin.readline())\nfor i in range(t):\n\tstdin.readline()\n\t(xa, ya) = map(int, stdin.readline().split())\n\t(xb, yb) = map(int, stdin.readline().split())\n\t(xf, yf) = map(int, stdin.readline().split())\n\td = abs(xa - xb) + abs(ya - yb)\n\tif xf == xa and xf == xb and (min(ya, yb) < yf < max(ya, yb)) or (yf == ya and yf == yb and (min(xa, xb) < xf < max(xa, xb))):\n\t\td += 2\n\tprint(d)\n", "t = int(input())\nfor i in range(t):\n\ts = input()\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\tf = [int(x) for x in input().split()]\n\t(xa, ya) = (a[0], a[1])\n\t(xb, yb) = (b[0], b[1])\n\t(xf, yf) = (f[0], f[1])\n\tif xa != xb and ya != yb:\n\t\tprint(abs(yb - ya) + abs(xb - xa))\n\telif (xf > xa and xf < xb or (xf < xa and xf > xb)) and (yf == ya or yf == yb) or ((yf > ya and yf < yb or (yf < ya and yf > yb)) and (xf == xa or xf == xb)):\n\t\tif yb == ya:\n\t\t\tprint(2 + abs(xb - xa))\n\t\telse:\n\t\t\tprint(2 + abs(yb - ya))\n\telif yb == ya:\n\t\tprint(abs(xb - xa))\n\telse:\n\t\tprint(abs(yb - ya))\n", "import sys\nimport bisect\n\ndef get_line():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef in1():\n\treturn int(input())\n\ndef decimalToBinary(n):\n\treturn bin(n).replace('0b', '')\nfor _ in range(in1()):\n\tt = get_line()\n\t(a1, a2) = get_line()\n\t(b1, b2) = get_line()\n\t(f1, f2) = get_line()\n\tif a1 == b1 and f1 == a1 and (f2 >= a2 and f2 <= b2 or (f2 >= b2 and f2 <= a2)):\n\t\tprint(abs(a1 - b1) + abs(a2 - b2) + 2)\n\telif a2 == b2 and f2 == a2 and (f1 >= a1 and f1 <= b1 or (f1 >= b1 and f1 <= a1)):\n\t\tprint(abs(a1 - b1) + abs(a2 - b2) + 2)\n\telse:\n\t\tprint(abs(a1 - b1) + abs(a2 - b2))\n", "import math\nfor i in range(int(input())):\n\temp = input()\n\t(xa, ya) = [int(x) for x in input().split()]\n\t(xb, yb) = [int(x) for x in input().split()]\n\t(xf, yf) = [int(x) for x in input().split()]\n\tif xa == xb == xf and ya == yb == yf:\n\t\tprint(0)\n\t\tcontinue\n\tif xa == xb == xf:\n\t\tif min(ya, yb) <= yf <= max(ya, yb):\n\t\t\tprint(abs(ya - yb) + 2)\n\t\telse:\n\t\t\tprint(abs(ya - yb))\n\t\tcontinue\n\tif ya == yb == yf:\n\t\tif min(xa, xb) <= xf <= max(xa, xb):\n\t\t\tprint(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tprint(abs(xa - xb))\n\t\tcontinue\n\tprint(abs(xa - xb) + abs(ya - yb))\n", "import math\nt = int(input())\nwhile t:\n\tinput()\n\t(a1, a2) = [int(x) for x in input().split()]\n\t(b1, b2) = [int(x) for x in input().split()]\n\t(f1, f2) = [int(x) for x in input().split()]\n\tif f1 - a1 != 0:\n\t\ta = (f2 - a2) / (f1 - a1)\n\telse:\n\t\ta = None\n\tif b1 - f1 != 0:\n\t\tb = (b2 - f2) / (b1 - f1)\n\telse:\n\t\tb = None\n\tf = math.sqrt((a2 - f2) ** 2 + (a1 - f1) ** 2)\n\tl = math.sqrt((a2 - b2) ** 2 + (a1 - b1) ** 2)\n\tm = math.sqrt((f2 - b2) ** 2 + (f1 - b1) ** 2)\n\tif a == b and l == f + m:\n\t\tif a1 == b1:\n\t\t\tprint(abs(b2 - a2) + 2)\n\t\telif a2 == b2:\n\t\t\tprint(abs(a1 - b1) + 2)\n\t\telse:\n\t\t\tprint(abs(a1 - b1) + abs(a2 - b2))\n\telse:\n\t\tprint(abs(a1 - b1) + abs(a2 - b2))\n\tt -= 1\n", "answers = []\n\ndef solve(xA, yA, xB, yB, xF, yF):\n\tif xA == xB:\n\t\tleast = min(yA, yB)\n\t\thighest = max(yA, yB)\n\t\tif (yF > least and yF < highest) and xA == xF:\n\t\t\tanswers.append(abs(yA - yB) + 2)\n\t\telse:\n\t\t\tanswers.append(abs(yA - yB))\n\telif yA == yB:\n\t\tleast = min(xA, xB)\n\t\thighest = max(xA, xB)\n\t\tif (xF > least and xF < highest) and yA == yF:\n\t\t\tanswers.append(abs(xA - xB) + 2)\n\t\telse:\n\t\t\tanswers.append(abs(xA - xB))\n\telse:\n\t\tanswers.append(abs(xA - xB) + abs(yA - yB))\nT = int(input())\nwhile T:\n\ttemp = input()\n\t(xA, yA) = [int(x) for x in input().split()]\n\t(xB, yB) = [int(x) for x in input().split()]\n\t(xF, yF) = [int(x) for x in input().split()]\n\tsolve(xA, yA, xB, yB, xF, yF)\n\tT -= 1\nfor ans in answers:\n\tprint(ans)\n", "from sys import stdin, stdout\ninput = stdin.readline\n\ndef main():\n\tt = int(input())\n\tfor z in range(t):\n\t\tinput()\n\t\t(x, y) = map(int, input().split())\n\t\t(x1, y1) = map(int, input().split())\n\t\t(x2, y2) = map(int, input().split())\n\t\tans = abs(x - x1) + abs(y - y1)\n\t\tif x == x1 and x2 == x or (y == y1 and y2 == y):\n\t\t\tx3 = min(x1, x)\n\t\t\tx4 = max(x1, x)\n\t\t\ty3 = min(y1, y)\n\t\t\ty4 = max(y1, y)\n\t\t\tif x3 <= x2 and x4 >= x2 and (y3 <= y2) and (y4 >= y2):\n\t\t\t\tans += 2\n\t\tprint(ans)\nmain()\n", "for testcase in range(int(input())):\n\tinput()\n\t(XA, YA) = map(int, input().split())\n\t(XB, YB) = map(int, input().split())\n\t(XF, YF) = map(int, input().split())\n\thorizontalDistance = abs(XA - XB)\n\tverticalDistance = abs(YA - YB)\n\tshortestPathLength = horizontalDistance + verticalDistance\n\tif XA == XB == XF and (YA < YF < YB or YB < YF < YA) or (YA == YB == YF and (XA < XF < XB or XB < XF < XA)):\n\t\tshortestPathLength += 2\n\tprint(shortestPathLength)\n", "t = int(input())\nresults = []\nfor i in range(t):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 != x2 and y1 != y2:\n\t\tresults.append(abs(x1 - x2) + abs(y1 - y2))\n\t\tcontinue\n\tif x1 == x2 != x3 and y1 != y2:\n\t\tresults.append(abs(x1 - x2) + abs(y1 - y2))\n\t\tcontinue\n\tif y1 == y2 != y3 and x1 != x2:\n\t\tresults.append(abs(x1 - x2) + abs(y1 - y2))\n\t\tcontinue\n\tif x1 == x2 == x3:\n\t\tif y1 > y3 > y2 or y2 > y3 > y1:\n\t\t\tresults.append(abs(y1 - y2) + 2)\n\t\telse:\n\t\t\tresults.append(abs(y1 - y2))\n\t\tcontinue\n\tif y1 == y2 == y3:\n\t\tif x1 > x3 > x2 or x2 > x3 > x1:\n\t\t\tresults.append(abs(x1 - x2) + 2)\n\t\telse:\n\t\t\tresults.append(abs(x1 - x2))\n\t\tcontinue\nfor i in range(t):\n\tprint(results[i])\n", "from sys import stdin\n\ndef main():\n\tcases = int(stdin.readline().strip())\n\tfor _ in range(cases):\n\t\tstdin.readline()\n\t\t(xa, ya) = map(int, stdin.readline().split())\n\t\t(xb, yb) = map(int, stdin.readline().split())\n\t\t(xf, yf) = map(int, stdin.readline().split())\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb == xf and min(ya, yb) < yf < max(ya, yb) or (ya == yb == yf and min(xa, xb) < xf < max(xa, xb)):\n\t\t\tans += 2\n\t\tprint(ans)\nmain()\n", "import fileinput\n\ndef process(line):\n\tprint(line)\n\ndef main():\n\tit = fileinput.input()\n\tnum_cases = int(next(it))\n\tfor i in range(num_cases):\n\t\tnext(it)\n\t\t(x_a, y_a) = list(map(int, next(it).split()))\n\t\t(x_b, y_b) = list(map(int, next(it).split()))\n\t\t(x_f, y_f) = list(map(int, next(it).split()))\n\t\tif x_a == x_b == x_f and (y_a < y_f < y_b or y_b < y_f < y_a):\n\t\t\tprint(abs(y_b - y_a) + 2)\n\t\telif y_a == y_b == y_f and (x_a < x_f < x_b or x_b < x_f < x_a):\n\t\t\tprint(abs(x_b - x_a) + 2)\n\t\telse:\n\t\t\tprint(abs(x_b - x_a) + abs(y_b - y_a))\nmain()\n", "from sys import stdin, stderr\ninput = stdin.readline\n\ndef dbp(*args, **kwargs):\n\tprint(*args, file=stderr, **kwargs)\n\ndef get_int_list():\n\treturn [int(x) for x in input().strip().split()]\n\ndef do_thing():\n\tinput()\n\tstart = get_int_list()\n\tend = get_int_list()\n\tblock = get_int_list()\n\tif start[0] == end[0] == block[0]:\n\t\t(lo, hi) = sorted([start[1], end[1]])\n\t\tif lo < block[1] < hi:\n\t\t\treturn hi - lo - 1 + 3\n\telif start[1] == end[1] == block[1]:\n\t\t(lo, hi) = sorted([start[0], end[0]])\n\t\tif lo < block[0] < hi:\n\t\t\treturn hi - lo - 1 + 3\n\treturn abs(end[0] - start[0]) + abs(end[1] - start[1])\n\ndef multicase():\n\tmaxcc = int(input().strip())\n\tfor cc in range(maxcc):\n\t\tprint(do_thing())\nmulticase()\n", "def main():\n\tt = int(input())\n\tfor i in range(t):\n\t\tinput()\n\t\t(xa, ya) = map(int, input().split())\n\t\t(xb, yb) = map(int, input().split())\n\t\t(xc, yc) = map(int, input().split())\n\t\tif xa != xb and ya != yb:\n\t\t\tprint(abs(xa - xb) + abs(ya - yb))\n\t\telse:\n\t\t\t(xl, xr) = (xa, xb) if xa < xb else (xb, xa)\n\t\t\t(yl, yr) = (ya, yb) if ya < yb else (yb, ya)\n\t\t\tif xa == xb == xc and yl < yc < yr:\n\t\t\t\tprint(2 + yr - yl)\n\t\t\t\tcontinue\n\t\t\tif ya == yb == yc and xl < xc < xr:\n\t\t\t\tprint(2 + xr - xl)\n\t\t\t\tcontinue\n\t\t\tprint(xr - xl + yr - yl)\nwhile True:\n\ttry:\n\t\tmain()\n\texcept:\n\t\tbreak\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa ^ xb and ya ^ yb:\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\telse:\n\t\tans = abs(xa - xb) + abs(ya - yb)\n\t\tif xa == xb == xf:\n\t\t\tif ya < yf < yb or yb < yf < ya:\n\t\t\t\tans += 2\n\t\tif ya == yb == yf:\n\t\t\tif xa < xf < xb or xb < xf < xa:\n\t\t\t\tans += 2\n\tprint(ans)\n", "n = int(input())\nres = []\nfor i in range(n):\n\tinput()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\tif a[0] != b[0] and a[1] != b[1]:\n\t\tres.append(abs(a[0] - b[0]) + abs(a[1] - b[1]))\n\telif a[0] == b[0]:\n\t\tif a[0] == f[0] and (a[1] < f[1] < b[1] or a[1] > f[1] > b[1]):\n\t\t\tres.append(abs(a[1] - b[1]) + 2)\n\t\telse:\n\t\t\tres.append(abs(a[1] - b[1]))\n\telif a[1] == b[1]:\n\t\tif a[1] == f[1] and (a[0] < f[0] < b[0] or a[0] > f[0] > b[0]):\n\t\t\tres.append(abs(a[0] - b[0]) + 2)\n\t\telse:\n\t\t\tres.append(abs(a[0] - b[0]))\nfor i in res:\n\tprint(i)\n", "t = int(input())\nwhile t:\n\tx = input()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tif a[0] == b[0] == c[0]:\n\t\tif a[1] < c[1] < b[1] or b[1] < c[1] < a[1]:\n\t\t\tans = abs(a[1] - b[1]) + 2\n\t\t\tprint(ans)\n\t\telse:\n\t\t\tprint(abs(a[1] - b[1]))\n\telif a[1] == b[1] == c[1]:\n\t\tif a[0] < c[0] < b[0] or b[0] < c[0] < a[0]:\n\t\t\tans = abs(a[0] - b[0]) + 2\n\t\t\tprint(ans)\n\t\telse:\n\t\t\tprint(abs(a[0] - b[0]))\n\telse:\n\t\tprint(abs(a[0] - b[0]) + abs(a[1] - b[1]))\n\tt -= 1\n", "try:\n\tt = int(input())\n\tfor _ in range(t):\n\t\tinput()\n\t\t(xa, ya) = [int(x) for x in input().split()]\n\t\t(xb, yb) = [int(x) for x in input().split()]\n\t\t(xf, yf) = [int(x) for x in input().split()]\n\t\tif xa == xb and xb == xf and (min(ya, yb) < yf and max(ya, yb) > yf):\n\t\t\tprint(abs(ya - yb) + 2)\n\t\telif ya == yb and yb == yf and (min(xa, xb) < xf and max(xa, xb) > xf):\n\t\t\tprint(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tprint(abs(xa - xb) + abs(ya - yb))\nexcept Exception as e:\n\tprint(e)\n", "for _ in range(int(input())):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa == xb == xf:\n\t\ta = min(ya, yb)\n\t\tb = max(ya, yb)\n\t\tif a <= yf <= b:\n\t\t\tprint(abs(ya - yb) + 2)\n\t\telse:\n\t\t\tprint(abs(ya - yb))\n\telif ya == yb == yf:\n\t\tc = min(xa, xb)\n\t\td = max(xa, xb)\n\t\tif c <= xf <= d:\n\t\t\tprint(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tprint(abs(xa - xb))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "t = int(input())\nwhile t:\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tif xa == xb == xf and min(ya, yb) < yf and (max(ya, yb) > yf):\n\t\tprint(abs(ya - yb) + 2)\n\telif ya == yb == yf and min(xa, xb) < xf and (max(xa, xb) > xf):\n\t\tprint(abs(xa - xb) + 2)\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n\tt -= 1\n", "def abs(x):\n\tif x > 0:\n\t\treturn x\n\telse:\n\t\treturn -x\n\ndef minLength(start, stop, obs):\n\tif start[0] != stop[0] and start[1] != stop[1]:\n\t\treturn abs(start[0] - stop[0]) + abs(start[1] - stop[1])\n\telif start[0] == stop[0] and start[0] == obs[0] and (abs(start[1]) < abs(obs[1]) < abs(stop[1]) or abs(stop[1]) < abs(obs[1]) < abs(start[1])):\n\t\treturn abs(start[1] - stop[1]) + 2\n\telif start[1] == stop[1] and start[1] == obs[1] and (abs(start[0]) < abs(obs[0]) < abs(stop[0]) or abs(stop[0]) < abs(obs[0]) < abs(start[0])):\n\t\treturn abs(start[0] - stop[0]) + 2\n\telse:\n\t\treturn abs(start[0] - stop[0]) + abs(start[1] - stop[1])\n\ndef shortestPath():\n\tncases = int(input())\n\tfor case in range(ncases):\n\t\tgap = input()\n\t\tstart = tuple(map(int, input().split()))\n\t\tstop = tuple(map(int, input().split()))\n\t\tobs = tuple(map(int, input().split()))\n\t\tprint(minLength(start, stop, obs))\nshortestPath()\n", "for _ in range(int(input())):\n\tinput()\n\tcolList = []\n\trowList = []\n\txsum = 0\n\tysum = 0\n\tfsum = 0\n\tx = list(map(int, input().split()))[:2]\n\ty = list(map(int, input().split()))[:2]\n\tf = list(map(int, input().split()))[:2]\n\tcolList.append(x[0])\n\tcolList.append(y[0])\n\tcolList.append(f[0])\n\trowList.append(x[1])\n\trowList.append(y[1])\n\trowList.append(f[1])\n\tif colList[0] == colList[1] == colList[2]:\n\t\tif rowList[0] < rowList[2] < rowList[1] or rowList[1] < rowList[2] < rowList[0]:\n\t\t\tval = abs(rowList[0] - rowList[1]) + 2\n\t\t\tprint(val)\n\t\telse:\n\t\t\tprint(abs(rowList[0] - rowList[1]))\n\telif rowList[0] == rowList[1] == rowList[2]:\n\t\tif colList[0] < colList[2] < colList[1] or colList[1] < colList[2] < colList[0]:\n\t\t\tval = abs(colList[0] - colList[1]) + 2\n\t\t\tprint(val)\n\t\telse:\n\t\t\tprint(abs(colList[0] - colList[1]))\n\telse:\n\t\tv = abs(colList[0] - colList[1]) + abs(rowList[0] - rowList[1])\n\t\tprint(v)\n", "from sys import stdin\nt = int(stdin.readline())\nfor i in range(t):\n\tstdin.readline()\n\t(xa, ya) = map(int, stdin.readline().split())\n\t(xb, yb) = map(int, stdin.readline().split())\n\t(xf, yf) = map(int, stdin.readline().split())\n\tprint(abs(xa - xb) + abs(ya - yb) + 2 * ((xa == xb == xf) * (yf - ya) * (yf - yb) | (ya == yb == yf) * (xf - xa) * (xf - xb) < 0))\n", "def solve():\n\tq = input()\n\t(xa, ya) = [int(i) for i in input().split()]\n\t(xb, yb) = [int(i) for i in input().split()]\n\t(xf, yf) = [int(i) for i in input().split()]\n\tif xa == xf and xf == xb and (yf > ya and yf < yb or (yf < ya and yf > yb)) or (ya == yf and yf == yb and (xf > xa and xf < xb or (xf < xa and xf > xb))):\n\t\treturn abs(ya - yb) + 2 + abs(xa - xb)\n\treturn abs(xa - xb) + abs(ya - yb)\nt = int(input())\nans = []\nwhile t:\n\tans.append(str(solve()))\n\tt -= 1\nprint('\\n'.join(ans))\n", "from sys import stdin, stdout\ninput = stdin.readline\nt = int(input())\nfor _ in range(t):\n\ttemp = input()\n\t(a, b) = map(int, input().split())\n\t(c, d) = map(int, input().split())\n\t(e, f) = map(int, input().split())\n\tans = abs(a - c) + abs(b - d)\n\tif a == c == e and (b < f < d or d < f < b):\n\t\tans += 2\n\tif b == d == f and (a < e < c or c < e < a):\n\t\tans += 2\n\tprint(ans)\n", "for _ in range(int(input())):\n\tempt = input()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\tcount = 0\n\tcheck = False\n\tif a[0] <= b[0] and a[1] <= b[1]:\n\t\tpass\n\telse:\n\t\t(a, b) = (b, a)\n\tif a[0] == b[0] == f[0] and a[1] < f[1] < b[1]:\n\t\tcheck = True\n\telif a[1] == b[1] == f[1] and a[0] < f[0] < b[0]:\n\t\tcheck = True\n\tcount += abs(a[0] - b[0])\n\tcount += abs(a[1] - b[1])\n\tif check:\n\t\tcount += 2\n\t\tprint(count)\n\telse:\n\t\tprint(count)\n", "import sys\nt = int(sys.stdin.readline())\nwhile t > 0:\n\tsp = sys.stdin.readline()\n\t(xa, ya) = map(int, sys.stdin.readline().split())\n\t(xb, yb) = map(int, sys.stdin.readline().split())\n\t(xf, yf) = map(int, sys.stdin.readline().split())\n\tans = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb and xa == xf:\n\t\tif yf < ya and yf > yb or (yf < yb and yf > ya):\n\t\t\tans += 2\n\tif ya == yb and ya == yf:\n\t\tif xf < xa and xf > xb or (xf < xb and xf > xa):\n\t\t\tans += 2\n\tprint(ans)\n\tt -= 1\n", "for input_number in range(int(input())):\n\tinput()\n\t(xA, yA) = map(int, input().split())\n\t(xB, yB) = map(int, input().split())\n\t(xF, yF) = map(int, input().split())\n\tif xB != xA and yB != yA:\n\t\tprint(abs(xA - xB) + abs(yA - yB))\n\tif xB == xA:\n\t\tif xA == xF and yF > min(yA, yB) and (yF < max(yA, yB)):\n\t\t\tprint(abs(yA - yB) + 2)\n\t\telse:\n\t\t\tprint(abs(yA - yB))\n\telif yA == yB:\n\t\tif yA == yF and xF > min(xA, xB) and (xF < max(xA, xB)):\n\t\t\tprint(abs(xA - xB) + 2)\n\t\telse:\n\t\t\tprint(abs(xA - xB))\n", "for _ in range(int(input())):\n\tinput()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\tif ax != bx and ay != by:\n\t\tprint(abs(ax - bx) + abs(ay - by))\n\telif ay == by == fy and (ax < fx < bx or bx < fx < ax):\n\t\tprint(abs(ax - bx) + abs(ay - by) + 2)\n\telif ax == bx == fx and (ay < fy < by or by < fy < ay):\n\t\tprint(abs(ax - bx) + abs(ay - by) + 2)\n\telse:\n\t\tprint(abs(ax - bx) + abs(ay - by))\n", "def is_between(xA: int, yA: int, xB: int, yB: int, xF: int, yF: int) -> bool:\n\tif xA == xB and xB == xF:\n\t\tlength_AB = abs(yA - yB)\n\t\tlength_AF = abs(yF - yA)\n\t\tlength_BF = abs(yB - yF)\n\t\tif length_AB == length_AF + length_BF:\n\t\t\treturn True\n\tif yA == yB and yB == yF:\n\t\tlength_AB = abs(xA - xB)\n\t\tlength_AF = abs(xF - xA)\n\t\tlength_BF = abs(xB - xF)\n\t\tif length_AB == length_AF + length_BF:\n\t\t\treturn True\n\treturn False\n\ndef shortest_path_length(xA: int, yA: int, xB: int, yB: int, xF: int, yF: int) -> int:\n\tpath_length = abs(xB - xA) + abs(yB - yA)\n\tif is_between(xA, yA, xB, yB, xF, yF):\n\t\tpath_length += 2\n\treturn path_length\nn = int(input())\nfor _ in range(n):\n\tinput()\n\t(xA, yA) = list(map(int, input().split()))\n\t(xB, yB) = list(map(int, input().split()))\n\t(xF, yF) = list(map(int, input().split()))\n\tprint(shortest_path_length(xA, yA, xB, yB, xF, yF))\n", "t = int(input())\nnatija = []\nfor i in range(t):\n\tinput()\n\t(x1, y1) = input().split(' ')\n\t(x1, y1) = (int(x1), int(y1))\n\t(x2, y2) = input().split(' ')\n\t(x2, y2) = (int(x2), int(y2))\n\t(x3, y3) = input().split(' ')\n\t(x3, y3) = (int(x3), int(y3))\n\tif x1 == x2 and x1 == x3 and (y1 <= y3 and y3 <= y2 or (y2 <= y3 and y3 <= y1)) or ((y1 == y2 and y1 == y3) and (x1 <= x3 and x3 <= x2 or (x2 <= x3 and x3 <= x1))):\n\t\tnatija.append(abs(x1 - x2) + abs(y1 - y2) + 2)\n\telse:\n\t\tnatija.append(abs(x1 - x2) + abs(y1 - y2))\nfor i in range(t):\n\tprint(natija[i])\n", "def is_f_between(a, b, f):\n\t(xa, ya) = a\n\t(xb, yb) = b\n\t(xf, yf) = f\n\treturn xa == xb == xf and (ya > yf and yf > yb or (ya < yf and yf < yb)) or (ya == yb == yf and (xa > xf and xf > xb or (xa < xf and xf < xb)))\nt = int(input())\nA = [[0, 0]] * t\nB = [[0, 0]] * t\nF = [[0, 0]] * t\nS = [0] * t\nfor i in range(t):\n\tinput()\n\tA[i] = list(map(int, input().split()))\n\tB[i] = list(map(int, input().split()))\n\tF[i] = list(map(int, input().split()))\n\t(xa, ya) = A[i]\n\t(xb, yb) = B[i]\n\t(xf, yf) = F[i]\n\tS[i] = abs(xa - xb) + abs(ya - yb)\n\tif is_f_between(A[i], B[i], F[i]):\n\t\tS[i] += 2\nfor i in range(t):\n\tprint(S[i])\n", "t = int(input())\nanswers = []\nfor i in range(t):\n\ta = input()\n\t(xa, ya) = map(int, input().split(' '))\n\t(xb, yb) = map(int, input().split(' '))\n\t(xf, yf) = map(int, input().split(' '))\n\tif xa != xb and ya != yb:\n\t\tanswers.append(abs(xa - xb) + abs(ya - yb))\n\telif yf == ya == yb:\n\t\tif xa - xb < 0 and xa < xf < xb or (xa - xb > 0 and xa > xf > xb):\n\t\t\tanswers.append(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tanswers.append(abs(xa - xb))\n\telif xf == xa == xb:\n\t\tif ya - yb < 0 and ya < yf < yb or (ya - yb > 0 and ya > yf > yb):\n\t\t\tanswers.append(abs(ya - yb) + 2)\n\t\telse:\n\t\t\tanswers.append(abs(ya - yb))\n\telse:\n\t\tanswers.append(abs(xa - xb) + abs(ya - yb))\nfor i in range(t):\n\tprint(answers[i])\n", "def func(a, b, f):\n\tif a[0] == b[0] and a[0] == f[0] and (min(a[1], b[1]) <= f[1] <= max(a[1], b[1])):\n\t\treturn abs(a[0] - b[0]) + abs(a[1] - b[1]) + 2\n\telif a[1] == b[1] and a[1] == f[1] and (min(a[0], b[0]) <= f[0] <= max(a[0], b[0])):\n\t\treturn abs(a[0] - b[0]) + abs(a[1] - b[1]) + 2\n\treturn abs(a[0] - b[0]) + abs(a[1] - b[1])\nt = int(input())\nfor _ in range(t):\n\tspace = input()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\tprint(func(a, b, f))\n", "test_num = int(input())\nfor test in range(test_num):\n\tinput()\n\t(xa, ya) = input().split()\n\txa = int(xa)\n\tya = int(ya)\n\t(xb, yb) = input().split()\n\txb = int(xb)\n\tyb = int(yb)\n\t(xf, yf) = input().split()\n\txf = int(xf)\n\tyf = int(yf)\n\tif xa == xb:\n\t\tif xf == xa and (ya < yf and yf < yb or (ya > yf and yf > yb)):\n\t\t\tprint(abs(yb - ya) + 2)\n\t\telse:\n\t\t\tprint(abs(yb - ya))\n\telif ya == yb:\n\t\tif yf == ya and (xa < xf and xf < xb or (xa > xf and xf > xb)):\n\t\t\tprint(abs(xb - xa) + 2)\n\t\telse:\n\t\t\tprint(abs(xb - xa))\n\telse:\n\t\tprint(abs(xb - xa) + abs(yb - ya))\n", "t = int(input())\nfor _ in range(t):\n\tinput()\n\tarr = list(map(int, input().split()))\n\txa = arr[0]\n\tya = arr[1]\n\tarr = list(map(int, input().split()))\n\txb = arr[0]\n\tyb = arr[1]\n\tarr = list(map(int, input().split()))\n\txf = arr[0]\n\tyf = arr[1]\n\tif xa == xb:\n\t\tif xa == xf and yf > min(ya, yb) and (yf < max(ya, yb)):\n\t\t\tprint(abs(ya - yb) + 2)\n\t\telse:\n\t\t\tprint(abs(ya - yb))\n\telif ya == yb:\n\t\tif yf == ya and xf > min(xa, xb) and (xf < max(xa, xb)):\n\t\t\tprint(abs(xa - xb) + 2)\n\t\telse:\n\t\t\tprint(abs(xa - xb))\n\telse:\n\t\tprint(abs(xa - xb) + abs(ya - yb))\n", "tests = int(input())\nfor _ in range(tests):\n\tinput()\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tf = list(map(int, input().split()))\n\t(x, y) = (abs(a[0] - b[0]), abs(a[1] - b[1]))\n\tif x == 0 and min(a[1], b[1]) < f[1] < max(a[1], b[1]) and (f[0] == a[0]):\n\t\tprint(x + y + 2)\n\telif y == 0 and min(a[0], b[0]) < f[0] < max(a[0], b[0]) and (f[1] == a[1]):\n\t\tprint(x + y + 2)\n\telse:\n\t\tprint(x + y)\n", "n = int(input())\ns = str(input())\nwhile n > 0:\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tif n != 1:\n\t\tq = str(input())\n\tans = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\tif a[0] == b[0] and a[0] == c[0] and (min(a[1], b[1]) < c[1]) and (c[1] < max(a[1], b[1])) or (a[1] == b[1] and a[1] == c[1] and (min(a[0], b[0]) < c[0]) and (c[0] < max(a[0], b[0]))):\n\t\tans += 2\n\tn -= 1\n\tprint(ans)\n", "import sys\nimport math\nimport heapq\nfrom collections import defaultdict as dd\nfrom collections import OrderedDict as od\nfrom collections import deque\nfrom itertools import permutations as pp\nfrom itertools import combinations as cc\nfrom sys import stdin\nfrom functools import cmp_to_key\nfrom functools import lru_cache\nfrom bisect import bisect_left as bs_l\nfrom bisect import bisect_right as bs_r\ninput = sys.stdin.readline\nmod = 10 ** 9 + 7\nsys.setrecursionlimit(10 ** 5)\nT = int(input())\nfor _ in range(T):\n\ts = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\t(xx, yy) = (abs(xa - xb), abs(ya - yb))\n\tif xx == 0 and xf == xa and (ya < yf < yb or yb < yf < ya):\n\t\txx += 2\n\tif yy == 0 and yf == ya and (xa < xf < xb or xb < xf < xa):\n\t\tyy += 2\n\tprint(xx + yy)\n", "t = int(input())\nfor i in range(t):\n\tinput()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\ts = abs(xb - xa) + abs(yb - ya)\n\tif xa == xb and xb == xf:\n\t\tif yb < yf and yf < ya or (yb > yf and yf > ya):\n\t\t\tprint(s + 2)\n\t\telse:\n\t\t\tprint(s)\n\telif yb == ya and yb == yf:\n\t\tif xa < xf and xf < xb or (xa > xf and xf > xb):\n\t\t\tprint(s + 2)\n\t\telse:\n\t\t\tprint(s)\n\telse:\n\t\tprint(s)\n", "t = int(input())\nfor _ in range(t):\n\tinput()\n\t(Xa, Ya) = map(int, input().split())\n\t(Xb, Yb) = map(int, input().split())\n\t(Xf, Yf) = map(int, input().split())\n\tans = abs(Xa - Xb) + abs(Ya - Yb)\n\tif Xa == Xb == Xf and (Ya < Yf < Yb or Yb < Yf < Ya) or (Ya == Yb == Yf and (Xa < Xf < Xb or Xb < Xf < Xa)):\n\t\tans += 2\n\tprint(ans)\n", "a = int(input())\nsol = []\nfor i in range(a):\n\tinput()\n\t(ax, ay) = input().split()\n\t(bx, by) = input().split()\n\t(fx, fy) = input().split()\n\ty_dist = abs(int(ay) - int(by))\n\tx_dist = abs(int(ax) - int(bx))\n\tsum_dist = x_dist + y_dist\n\tif y_dist == 0 and int(fy) == int(ay) and (int(fx) > min(int(ax), int(bx))) and (int(fx) < max(int(ax), int(bx))):\n\t\tsum_dist = sum_dist + 2\n\telif x_dist == 0 and int(fx) == int(ax) and (int(fy) > min(int(ay), int(by))) and (int(fy) < max(int(ay), int(by))):\n\t\tsum_dist = sum_dist + 2\n\tsol.append(sum_dist)\nfor item in sol:\n\tprint(item)\n", "t = int(input())\nfor i in range(t):\n\tblank = input()\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\tf = [int(x) for x in input().split()]\n\ttotal = b[0] - a[0]\n\tif total < 0:\n\t\ttotal *= -1\n\ttotal2 = b[1] - a[1]\n\tif total2 < 0:\n\t\ttotal2 *= -1\n\tif total == 0 and f[0] == a[0] or (total2 == 0 and f[1] == a[1]):\n\t\tif f[0] == a[0]:\n\t\t\tif f[1] < a[1] and f[1] > b[1] or (f[1] > a[1] and f[1] < b[1]):\n\t\t\t\ttotal += 2\n\t\telif f[0] < a[0] and f[0] > b[0] or (f[0] > a[0] and f[0] < b[0]):\n\t\t\ttotal += 2\n\tprint(total + total2)\n", "ans = []\nfor i in range(int(input())):\n\ts = 0\n\tbuff = input()\n\t(q, w, e) = (input().split(), input().split(), input().split())\n\tif q[0] == w[0] == e[0]:\n\t\tif int(q[1]) < int(e[1]) < int(w[1]) or int(w[1]) < int(e[1]) < int(q[1]):\n\t\t\ts = 2\n\telif q[1] == w[1] == e[1]:\n\t\tif int(q[0]) < int(e[0]) < int(w[0]) or int(w[0]) < int(e[0]) < int(q[0]):\n\t\t\ts = 2\n\ts = s + abs(int(q[0]) - int(w[0])) + abs(int(q[1]) - int(w[1]))\n\tans.append(s)\nfor i in ans:\n\tprint(i, '\\n')\n", "from sys import stdin\ninput = stdin.readline\nrn = lambda : int(input())\nrns = lambda : map(int, input().split())\nrl = lambda : list(map(int, input().split()))\nrs = lambda : input().strip()\nYN = lambda x: print('YES') if x else print('NO')\nmod = 10 ** 9 + 7\nfor _ in range(rn()):\n\tinput()\n\t(a, A) = rns()\n\t(b, B) = rns()\n\t(f, F) = rns()\n\tans = abs(a - b) + abs(A - B)\n\tif a == b and A == B:\n\t\tpass\n\telif a == b == f:\n\t\t(l, r) = sorted([A, B])\n\t\tif l <= F <= r:\n\t\t\tans += 2\n\telif A == B == F:\n\t\t(l, r) = sorted([a, b])\n\t\tif l <= f <= r:\n\t\t\tans += 2\n\telse:\n\t\tpass\n\tprint(ans)\n", "import sys\nimport math\nfrom sys import stdin, stdout\n\ndef get_ints_in_variables():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef get_int():\n\treturn int(input())\n\ndef get_ints_in_list():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef get_list_of_list(n):\n\treturn [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]\n\ndef get_string():\n\treturn sys.stdin.readline().strip()\n\ndef main():\n\tfor _ in range(get_int()):\n\t\ttmp = input()\n\t\t(Ay, Ax) = get_ints_in_variables()\n\t\t(By, Bx) = get_ints_in_variables()\n\t\t(Fy, Fx) = get_ints_in_variables()\n\t\tcount = 0\n\t\tif Ax == Bx and Bx == Fx and (Ay <= Fy <= By or By <= Fy <= Ay):\n\t\t\tcount += abs(Ay - By) + abs(Ax - Bx)\n\t\t\tcount += 2\n\t\telif Ay == By and By == Fy and (Ax <= Fx <= Bx or Bx <= Fx <= Ax):\n\t\t\tcount += abs(Ay - By) + abs(Ax - Bx)\n\t\t\tcount += 2\n\t\telse:\n\t\t\tcount += abs(Ay - By) + abs(Ax - Bx)\n\t\tprint(count)\nmain()\n", "x = int(input())\nfor i in range(x):\n\tp = input()\n\t(al, ah) = map(int, input().split())\n\t(bl, bh) = map(int, input().split())\n\t(fl, fh) = map(int, input().split())\n\tif al == bl and al == fl and (abs(ah - bh) == abs(fh - ah) + abs(fh - bh)):\n\t\tprint(abs(ah - bh) + 2)\n\telif ah == bh == fh and abs(al - bl) == abs(fl - al) + abs(fl - bl):\n\t\tprint(abs(al - bl) + 2)\n\telse:\n\t\tprint(abs(al - bl) + abs(ah - bh))\n", "t = int(input())\nfor _ in range(t):\n\ttmp = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tres = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb == xf and min(ya, yb) <= yf <= max(ya, yb) or (ya == yb == yf and min(xa, xb) <= xf <= max(xa, xb)):\n\t\tres += 2\n\tprint(res)\n", "T = int(input())\nout = []\nfor t in range(T):\n\t_ = input()\n\t(ca, ra) = [int(x) for x in input().split()]\n\t(cb, rb) = [int(x) for x in input().split()]\n\t(cf, rf) = [int(x) for x in input().split()]\n\treq = abs(cb - ca) + abs(rb - ra)\n\tif ca == cb == cf and (ra <= rf <= rb or rb <= rf <= ra):\n\t\treq += 2\n\telif ra == rb == rf and (ca <= cf <= cb or cb <= cf <= ca):\n\t\treq += 2\n\tout.append(req)\nfor e in out:\n\tprint(e)\n", "t = int(input())\nfor i in range(t):\n\ttrash = input()\n\t(Ax, Ay) = map(int, input().split())\n\t(Bx, By) = map(int, input().split())\n\t(Fx, Fy) = map(int, input().split())\n\tif Ax != Bx and Ay != By:\n\t\tprint(abs(Ax - Bx) + abs(Ay - By))\n\telif Ax == Bx and Ay != By:\n\t\tif Fx == Ax and min(Ay, By) < Fy < max(Ay, By):\n\t\t\tprint(abs(Ay - By) + 2)\n\t\telse:\n\t\t\tprint(abs(Ay - By))\n\telif Ay == By and Ax != Bx:\n\t\tif Fy == Ay and min(Ax, Bx) < Fx < max(Ax, Bx):\n\t\t\tprint(abs(Ax - Bx) + 2)\n\t\telse:\n\t\t\tprint(abs(Ax - Bx))\n\telse:\n\t\tprint(0)\n", "import math as mt\nimport sys\n\ndef rint():\n\treturn int(sys.stdin.readline())\n\ndef rarr(typ):\n\treturn map(typ, sys.stdin.readline().split())\n\ndef rmult(typ):\n\treturn map(typ, sys.stdin.readlines().split())\n\ndef main(a, b, f):\n\n\tdef dist(p, q):\n\t\treturn abs(p[0] - q[0]) + abs(p[1] - q[1])\n\tans = dist(a, b)\n\tif a[0] == b[0] == f[0] or a[1] == b[1] == f[1]:\n\t\tif dist(a, f) + dist(b, f) == ans:\n\t\t\tans += 2\n\treturn ans\nt = rint()\nfor _ in range(t):\n\tinput()\n\ta = tuple(rarr(int))\n\tb = tuple(rarr(int))\n\tf = tuple(rarr(int))\n\tprint(main(a, b, f))\n", "n = int(input())\nfor i in range(n):\n\tA = input()\n\t(x, y) = map(int, input().split())\n\t(a, b) = input().split()\n\t(fx, fy) = input().split()\n\tx = int(x)\n\ty = int(y)\n\ta = int(a)\n\tb = int(b)\n\tfx = int(fx)\n\tfy = int(fy)\n\tif b < y:\n\t\tm = b\n\t\tb = y\n\t\ty = m\n\tif a < x:\n\t\tm = a\n\t\ta = x\n\t\tx = m\n\tl = abs(y - b) + abs(x - a)\n\tif fx == x and fx == a and (fy < b) and (fy > y):\n\t\tl = l + 2\n\telif fy == y and fy == b and (fx < a) and (fx > x):\n\t\tl = l + 2\n\tprint(l)\n", "T = int(input())\nfor case in range(T):\n\ta = input()\n\t(x, y) = list(map(int, input().split()))\n\t(i, j) = list(map(int, input().split()))\n\t(dx, dy) = list(map(int, input().split()))\n\tif i != x and j != y:\n\t\tprint(abs(x - i) + abs(y - j))\n\telif i == x and i == dx:\n\t\tmaxi = max(y, j)\n\t\tmini = min(y, j)\n\t\tif mini < dy < maxi:\n\t\t\tprint(maxi - mini + 2)\n\t\telse:\n\t\t\tprint(maxi - mini)\n\telif j == y and j == dy:\n\t\tmaxi = max(x, i)\n\t\tmini = min(x, i)\n\t\tif mini < dx < maxi:\n\t\t\tprint(maxi - mini + 2)\n\t\telse:\n\t\t\tprint(maxi - mini)\n\telse:\n\t\tprint(abs(x - i) + abs(y - j))\n", "for _ in range(int(input())):\n\tinput()\n\t(aa, ab) = map(int, input().split())\n\t(ba, bb) = map(int, input().split())\n\t(fa, fb) = map(int, input().split())\n\tif ab == bb == fb and (aa < fa < ba or ba < fa < aa):\n\t\tprint(abs(aa - ba) + abs(ab - bb) + 2)\n\telif aa == ba == fa and (ab < fb < bb or bb < fb < ab):\n\t\tprint(abs(aa - ba) + abs(ab - bb) + 2)\n\telse:\n\t\tprint(abs(aa - ba) + abs(ab - bb))\n", "N = int(input())\narr = []\ncoord = []\ncoord = [[0 for j in range(2)] for i in range(3)]\nfor i in range(N):\n\tarr.append(0)\nfor i in range(N):\n\tinput()\n\t(coord[0][0], coord[0][1]) = map(int, input().split())\n\t(coord[1][0], coord[1][1]) = map(int, input().split())\n\t(coord[2][0], coord[2][1]) = map(int, input().split())\n\tarr[i] = abs(coord[1][0] - coord[0][0]) + abs(coord[1][1] - coord[0][1])\n\tif coord[0][0] == coord[1][0] and coord[1][0] == coord[2][0] and (abs(coord[0][1] - coord[2][1]) + abs(coord[2][1] - coord[1][1]) == abs(coord[1][1] - coord[0][1])) or (coord[0][1] == coord[1][1] and coord[1][1] == coord[2][1] and (abs(coord[0][0] - coord[2][0]) + abs(coord[2][0] - coord[1][0]) == abs(coord[1][0] - coord[0][0]))):\n\t\tarr[i] += 2\nfor i in range(N):\n\tprint(arr[i])\n", "t = int(input())\nfor i in range(t):\n\ts = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tc = 0\n\tif xa == xb == xf and (ya < yf < yb or ya > yf > yb):\n\t\tc = 2\n\tif ya == yb == yf and (xa < xf < xb or xa > xf > xb):\n\t\tc = 2\n\tprint(abs(xa - xb) + abs(ya - yb) + c)\n", "def ques1():\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\ttotal_steps = 0\n\ttotal_steps += abs(x1 - x2) + abs(y1 - y2)\n\tif x1 == x3 and x2 == x3:\n\t\tmin_y = min(y1, y2)\n\t\tmax_y = max(y1, y2)\n\t\tif y3 > min_y and y3 < max_y:\n\t\t\ttotal_steps += 2\n\telif y1 == y3 and y2 == y3:\n\t\tmin_x = min(x1, x2)\n\t\tmax_x = max(x1, x2)\n\t\tif x3 > min_x and x3 < max_x:\n\t\t\ttotal_steps += 2\n\treturn total_steps\nnumber_of_testcases = int(input())\ninput()\nfor i in range(number_of_testcases):\n\tprint(ques1())\n\tif i < number_of_testcases - 1:\n\t\tinput()\n", "import math\nimport itertools\nt = int(input())\nfor _ in range(t):\n\tinput()\n\t(x_a, y_a) = map(int, input().split())\n\t(x_b, y_b) = map(int, input().split())\n\t(x_f, y_f) = map(int, input().split())\n\tif x_a == x_b and x_a != x_f:\n\t\tprint(abs(y_a - y_b))\n\telif y_a == y_b and y_a != y_f:\n\t\tprint(abs(x_a - x_b))\n\telif x_a == x_b and x_a == x_f:\n\t\tif y_a > y_f > y_b or y_b > y_f > y_a:\n\t\t\tprint(abs(y_a - y_b) + 2)\n\t\telse:\n\t\t\tprint(abs(y_a - y_b))\n\telif y_a == y_b and y_a == y_f:\n\t\tif x_a > x_f > x_b or x_b > x_f > x_a:\n\t\t\tprint(abs(x_a - x_b) + 2)\n\t\telse:\n\t\t\tprint(abs(x_a - x_b))\n\telif x_a != x_b and y_a != y_b:\n\t\tprint(abs(x_a - x_b) + abs(y_a - y_b))\n", "import math\n\ndef getList(method=int):\n\treturn list(map(method, input().split()))\n\ndef getInt():\n\treturn int(input())\nfor _ in range(getInt()):\n\tinput()\n\t(xa, ya) = getList()\n\t(xb, yb) = getList()\n\t(xf, yf) = getList()\n\tans = abs(xa - xb) + abs(ya - yb)\n\tif xa == xb == xf and min(ya, yb) < yf < max(ya, yb) or (ya == yb == yf and min(xa, xb) < xf < max(xa, xb)):\n\t\tans += 2\n\tprint(ans)\n", "def path():\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\tif (ax == bx and bx == fx) and (fy > min(ay, by) and fy < max(ay, by)):\n\t\treturn abs(ay - by) + 2\n\telif (by == ay and by == fy) and (fx > min(ax, bx) and fx < max(ax, bx)):\n\t\treturn abs(ax - bx) + 2\n\telse:\n\t\treturn abs(ay - by) + abs(ax - bx)\nfor _ in range(int(input())):\n\tempty = str(input())\n\tprint(path())\n", "import sys\nfrom os import path\nimport collections\nfrom collections import defaultdict\nimport math\nif path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nt = int(sys.stdin.readline().rstrip())\nwhile t > 0:\n\tt -= 1\n\tm = input()\n\t(a1, a2) = map(int, sys.stdin.readline().rstrip().split())\n\t(b1, b2) = map(int, sys.stdin.readline().rstrip().split())\n\t(f1, f2) = map(int, sys.stdin.readline().rstrip().split())\n\tc = 0\n\tif a1 == b1 == f1:\n\t\tif b2 <= f2 <= a2 or a2 <= f2 <= b2:\n\t\t\tc = abs(b2 - a2) + 2\n\t\telse:\n\t\t\tc = abs(b2 - a2)\n\telif a2 == b2 == f2:\n\t\tif b1 <= f1 <= a1 or a1 <= f1 <= b1:\n\t\t\tc = abs(b1 - a1) + 2\n\t\telse:\n\t\t\tc = abs(b1 - a1)\n\telse:\n\t\tc = abs(a1 - b1) + abs(a2 - b2)\n\tprint(c)\n", "t = int(input())\ninput()\nfor tests in range(t):\n\ta = [int(i) for i in input().split(' ')]\n\tb = [int(i) for i in input().split(' ')]\n\tf = [int(i) for i in input().split(' ')]\n\tsteps = abs(a[0] - b[0]) + abs(a[1] - b[1])\n\tif a[0] == b[0] and a[0] == f[0] and (a[1] < f[1] < b[1] or b[1] < f[1] < a[1]):\n\t\tsteps += 2\n\tif a[1] == b[1] and a[1] == f[1] and (a[0] < f[0] < b[0] or b[0] < f[0] < a[0]):\n\t\tsteps += 2\n\tprint(steps)\n\tif tests < t - 1:\n\t\tinput()\n", "n = int(input())\nfor i in range(n):\n\tvide = input()\n\tdebut = list(map(int, input().split()))\n\tfin = list(map(int, input().split()))\n\tobstacle = list(map(int, input().split()))\n\tl = abs(fin[1] - debut[1]) + abs(fin[0] - debut[0])\n\tif fin[1] == debut[1] == obstacle[1] and (fin[0] < obstacle[0] < debut[0] or fin[0] > obstacle[0] > debut[0]):\n\t\tl += 2\n\telif fin[0] == debut[0] == obstacle[0] and (fin[1] < obstacle[1] < debut[1] or fin[1] > obstacle[1] > debut[1]):\n\t\tl += 2\n\tprint(l)\n", "for _ in range(int(input())):\n\tn = input()\n\t(xa, xb) = map(int, input().split())\n\t(ya, yb) = map(int, input().split())\n\t(za, zb) = map(int, input().split())\n\tst = abs(xa - ya) + abs(yb - xb)\n\tif xa == ya and xa == za and (xb < zb < yb or yb < zb < xb):\n\t\tst += 2\n\tif xb == yb and xb == zb and (xa < za < ya or ya < za < xa):\n\t\tst += 2\n\tprint(st)\n", "T = int(input())\nfor tc in range(1, T + 1):\n\tblank = input()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tif x1 == x2 == x3:\n\t\tif y1 > y2 and y2 <= y3 <= y1:\n\t\t\tprint(y1 - y2 + 2)\n\t\telif y1 < y2 and y1 <= y3 <= y2:\n\t\t\tprint(y2 - y1 + 2)\n\t\telse:\n\t\t\tprint(abs(y1 - y2))\n\telif y1 == y2 == y3:\n\t\tif x1 > x2 and x2 <= x3 <= x1:\n\t\t\tprint(x1 - x2 + 2)\n\t\telif x1 < x2 and x1 <= x3 <= x2:\n\t\t\tprint(x2 - x1 + 2)\n\t\telse:\n\t\t\tprint(abs(x1 - x2))\n\telse:\n\t\tprint(abs(x1 - x2) + abs(y1 - y2))\n", "test = int(input())\nfor _ in range(test):\n\tspace = input()\n\t(a1, a2) = map(int, input().split())\n\t(b1, b2) = map(int, input().split())\n\t(f1, f2) = map(int, input().split())\n\tans = 0\n\tif a1 == b1 == f1:\n\t\tif a2 < f2 < b2 or b2 < f2 < a2:\n\t\t\tans = abs(a2 - b2) + 2\n\t\telse:\n\t\t\tans = abs(a2 - b2)\n\telif a2 == b2 == f2:\n\t\tif a1 < f1 < b1 or b1 < f1 < a1:\n\t\t\tans = abs(a1 - b1) + 2\n\t\telse:\n\t\t\tans = abs(a1 - b1)\n\telse:\n\t\tans = abs(a1 - b1) + abs(a2 - b2)\n\tprint(ans)\n", "import math\nt = int(input())\nfor cs in range(t):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\t(x1, x2) = sorted([x1, x2])\n\t(y1, y2) = sorted([y1, y2])\n\tdist = abs(x1 - x2) + abs(y1 - y2)\n\tif any([len(set([x1, x2, x3])) == 1 and y1 <= y3 <= y2, len(set([y1, y2, y3])) == 1 and x1 <= x3 <= x2]):\n\t\tdist += 2\n\tprint(dist)\n", "for _ in range(int(input())):\n\ts = input()\n\t(ax, ay) = map(int, input().split())\n\t(bx, by) = map(int, input().split())\n\t(fx, fy) = map(int, input().split())\n\td = abs(bx - ax) + abs(by - ay)\n\tif (ax == bx and bx == fx) and min(ay, by) <= fy and (max(ay, by) >= fy):\n\t\td += 2\n\tif (ay == by and by == fy) and min(ax, bx) <= fx and (max(ax, bx) >= fx):\n\t\td += 2\n\tprint(d)\n", "for _ in ' ' * int(input()):\n\tblank = input()\n\t(xa, ya) = map(int, input().split())\n\t(xb, yb) = map(int, input().split())\n\t(xf, yf) = map(int, input().split())\n\tdist = abs(xb - xa) + abs(yb - ya)\n\tif xa == xb == xf and (ya < yf < yb or yb < yf < ya) or (ya == yb == yf and (xa < xf < xb or xb < xf < xa)):\n\t\tdist += 2\n\tprint(dist)\n", "t = int(input())\nfor _ in range(t):\n\ts = input()\n\t(a, b) = map(int, input().split())\n\t(c, d) = map(int, input().split())\n\t(e, f) = map(int, input().split())\n\tif a == c == e:\n\t\tif (f - b) * (f - d) < 0:\n\t\t\tprint(abs(d - b) + 2)\n\t\telse:\n\t\t\tprint(abs(d - b))\n\telif b == d == f:\n\t\tif (a - e) * (c - e) < 0:\n\t\t\tprint(abs(a - c) + 2)\n\t\telse:\n\t\t\tprint(abs(a - c))\n\telse:\n\t\tprint(abs(a - c) + abs(b - d))\n", "a = int(input())\ne = input()\nfor i in range(a):\n\t(a1, a2) = list(map(int, input().split()))\n\t(b1, b2) = list(map(int, input().split()))\n\t(f1, f2) = list(map(int, input().split()))\n\tif i != a - 1:\n\t\te = input()\n\tif a1 == b1 and f1 == a1 and (f2 > min(a2, b2) and f2 < max(a2, b2)):\n\t\tprint(abs(a1 - b1) + abs(a2 - b2) + 2)\n\telif a2 == b2 and f2 == b2 and (f1 > min(a1, b1)) and (f1 < max(a1, b1)):\n\t\tprint(abs(a1 - b1) + abs(a2 - b2) + 2)\n\telse:\n\t\tprint(abs(a1 - b1) + abs(a2 - b2))\n", "def func():\n\tc = int(input())\n\tk = []\n\tfor i in range(c):\n\t\tinput()\n\t\tm = []\n\t\tm.append(input())\n\t\tm.append(input())\n\t\tm.append(input())\n\t\tax = int(str(m[0]).split()[0])\n\t\tay = int(str(m[0]).split()[1])\n\t\tbx = int(str(m[1]).split()[0])\n\t\tby = int(str(m[1]).split()[1])\n\t\tfx = int(str(m[2]).split()[0])\n\t\tfy = int(str(m[2]).split()[1])\n\t\tif ax == bx:\n\t\t\tif fx == ax:\n\t\t\t\tif ay < by and fy < by and (fy > ay):\n\t\t\t\t\tk.append(abs(by - ay) + 2)\n\t\t\t\telif ay > by and fy < ay and (fy > by):\n\t\t\t\t\tk.append(abs(by - ay) + 2)\n\t\t\t\telse:\n\t\t\t\t\tk.append(abs(by - ay))\n\t\t\telse:\n\t\t\t\tk.append(abs(by - ay))\n\t\telif ay == by:\n\t\t\tif fy == ay:\n\t\t\t\tif ax < bx and fx < bx and (fx > ax):\n\t\t\t\t\tk.append(abs(bx - ax) + 2)\n\t\t\t\telif ax > bx and fx < ax and (fx > bx):\n\t\t\t\t\tk.append(abs(bx - ax) + 2)\n\t\t\t\telse:\n\t\t\t\t\tk.append(abs(bx - ax))\n\t\t\telse:\n\t\t\t\tk.append(abs(bx - ax))\n\t\telif ay != by and ax != bx:\n\t\t\tk.append(abs(bx - ax) + abs(by - ay))\n\tfor i in range(c):\n\t\tprint(k[i])\nfunc()\n", "import math\ninp = int(input())\nfor _ in range(inp):\n\tinput()\n\t(xa, ya) = map(int, input().split(' '))\n\t(xb, yb) = map(int, input().split(' '))\n\t(xc, yc) = map(int, input().split(' '))\n\tdist = abs(xa - xb) + abs(ya - yb)\n\tif math.sqrt((xa - xb) ** 2 + (ya - yb) ** 2) >= math.sqrt((xa - xc) ** 2 + (ya - yc) ** 2) and math.sqrt((xa - xb) ** 2 + (ya - yb) ** 2) >= math.sqrt((xb - xc) ** 2 + (yb - yc) ** 2):\n\t\tif xc == xa and xc == xb or (yc == ya and yc == yb):\n\t\t\tdist += 2\n\t\t\tprint(dist)\n\t\telse:\n\t\t\tprint(dist)\n\telse:\n\t\tprint(dist)\n", "import heapq, math\nfrom collections import defaultdict, deque\nfrom os import getcwd\nimport sys, os.path\nif os.path.exists('D:\\\\CP\\\\programs\\\\input.txt'):\n\tsys.stdout = open('D:\\\\CP\\\\programs\\\\output.txt', 'w')\n\tsys.stdin = open('D:\\\\CP\\\\programs\\\\input.txt', 'r')\ninput = sys.stdin.readline\ntest = int(input())\nfor _ in range(test):\n\tinput()\n\t(x1, y1) = map(int, input().split())\n\t(x2, y2) = map(int, input().split())\n\t(x3, y3) = map(int, input().split())\n\tdis = abs(x1 - x2) + abs(y1 - y2)\n\tif x1 == x2 and x2 == x3:\n\t\tif y3 > min(y1, y2) and y3 < max(y1, y2):\n\t\t\tdis += 2\n\telif y1 == y2 and y2 == y3:\n\t\tif x3 > min(x1, x2) and x3 < max(x1, x2):\n\t\t\tdis += 2\n\tprint(dis)\n", "import sys\n\ndef rl():\n\treturn sys.stdin.readline().strip()\n\ndef rl_types(types):\n\tstr_list = [x for x in sys.stdin.readline().strip().split(' ')]\n\treturn [types[i](str_list[i]) for i in range(len(str_list))]\n\ndef pr(something):\n\tsys.stdout.write(str(something) + '\\n')\n\ndef pra(array):\n\tsys.stdout.write(' '.join([str(x) for x in array]) + '\\n')\n\ndef solve(array):\n\treturn array\nNT = int(rl())\nfor ti in range(NT):\n\trl()\n\t(ax, ay) = [int(x) for x in rl().split(' ')]\n\t(bx, by) = [int(x) for x in rl().split(' ')]\n\t(fx, fy) = [int(x) for x in rl().split(' ')]\n\t(dx, dy) = (abs(bx - ax), abs(by - ay))\n\tdist = dx + dy\n\tif ax < fx < bx and ay == by and (ay == fy) or (ax > fx > bx and ay == by and (ay == fy)) or (ax == bx and ax == fx and (ay < fy < by)) or (ax == bx and ax == fx and (ay > fy > by)):\n\t\tdist += 2\n\tpr(dist)\n"]

difficulty: EASY

source: codeforces

raw_problem:
A. Shortest Path with Obstacle

time limit per test
2 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

There are three cells on an infinite 2-dimensional grid, labeled $$$A$$$, $$$B$$$, and $$$F$$$. Find the length of the shortest path from $$$A$$$ to $$$B$$$ if:

 in one move you can go to any of the four adjacent cells sharing a side;

 visiting the cell $$$F$$$ is forbidden (it is an obstacle).

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first one contains two integers $$$x_A, y_A$$$ ($$$1 \le x_A, y_A \le 1000$$$) — coordinates of the start cell $$$A$$$. The second one contains two integers $$$x_B, y_B$$$ ($$$1 \le x_B, y_B \le 1000$$$) — coordinates of the finish cell $$$B$$$. The third one contains two integers $$$x_F, y_F$$$ ($$$1 \le x_F, y_F \le 1000$$$) — coordinates of the forbidden cell $$$F$$$. All cells are distinct.

Coordinate $$$x$$$ corresponds to the column number and coordinate $$$y$$$ corresponds to the row number (see the pictures below).

Output

Output $$$t$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th test case: the length of the shortest path from the cell $$$A$$$ to the cell $$$B$$$ if the cell $$$F$$$ is not allowed to be visited.

Example

Input

7

1 1
3 3
2 2

2 5
2 1
2 3

1000 42
1000 1
1000 1000

1 10
3 10
2 10

3 8
7 8
3 7

2 1
4 1
1 1

1 344
1 10
1 1

Output

4
6
41
4
4
2
334

Note
  An example of a possible shortest path for the first test case.   An example of a possible shortest path for the second test case.

question:
There are three cells on an infinite 2-dimensional grid, labeled $$$A$$$, $$$B$$$, and $$$F$$$. Find the length of the shortest path from $$$A$$$ to $$$B$$$ if:
 -  in one move you can go to any of the four adjacent cells sharing a side; -  visiting the cell $$$F$$$ is forbidden (it is an obstacle).
Input
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow. Before each test case, there is an empty line.
Each test case contains three lines. The first one contains two integers $$$x_A, y_A$$$ ($$$1 \le x_A, y_A \le 1000$$$) — coordinates of the start cell $$$A$$$. The second one contains two integers $$$x_B, y_B$$$ ($$$1 \le x_B, y_B \le 1000$$$) — coordinates of the finish cell $$$B$$$. The third one contains two integers $$$x_F, y_F$$$ ($$$1 \le x_F, y_F \le 1000$$$) — coordinates of the forbidden cell $$$F$$$. All cells are distinct.
Coordinate $$$x$$$ corresponds to the column number and coordinate $$$y$$$ corresponds to the row number (see the pictures below).

Output
Output $$$t$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th test case: the length of the shortest path from the cell $$$A$$$ to the cell $$$B$$$ if the cell $$$F$$$ is not allowed to be visited.

Example
Input
7

1 1
3 3
2 2

2 5
2 1
2 3

1000 42
1000 1
1000 1000

1 10
3 10
2 10

3 8
7 8
3 7

2 1
4 1
1 1

1 344
1 10
1 1

Output
4
6
41
4
4
2
334

Note
 ![image](1.png) An example of a possible shortest path for the first test case.  ![image](2.png) An example of a possible shortest path for the second test case.

image_tags: Map Map

data_split: test