Given N points of the form (x_{i}, y_{i}) on a 2-D plane.

From each point, you draw 2 lines one horizontal and one vertical. Now some of the lines may overlap each other, therefore you are required to print the number of distinct lines you can see on the plane.

Note:
Two horizontal lines are distinct if they pass through different y coordinates.
Two vertical lines are distinct if they pass through different x coordinates.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single integer N, the number of points.
- The next N lines contain two space separated integers x_{i}, y_{i}, the coordinate of the i^{th} point.

------ Output Format ------ 

For each testcase, output in a single line the number of distinct lines that can be seen on the plane.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ X_{i}, Y_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases is atmost $10^{5}$.

----- Sample Input 1 ------ 
3
4
1 1
1 0
0 1
0 0
5
0 0
0 1
0 2
0 3
0 4
1
10 10
----- Sample Output 1 ------ 
4
6
2
----- explanation 1 ------ 
Test Case $1$: There are $2$ horizontal lines passing through $Y = 0$ and $Y = 1$, and $2$  vertical lines passing through $X = 0$ and $X = 1$.

.png =500x500)

Test Case $2$: There are $5$ horizontal lines passing through $Y = 0, Y = 1, Y = 2, Y = 3$ and $Y = 4$ and $1$ vertical line passing through $X = 0$.

Test Case $3$: There is $1$ horizontal line passing through $Y = 10$ and $1$ vertical line passing through $X = 10$.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
n = int(input())
for i in range(n):
	k = int(input())
	l1 = []
	l2 = []
	for i in range(k):
		(a, b) = map(int, input().split())
		l1.append(a)
		l2.append(b)
	print(len(set(l1)) + len(set(l2)))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	X = []
	Y = []
	for i in range(n):
		(x, y) = map(int, input().split())
		X.append(x)
		Y.append(y)
	sys.stdout.write(str(len(set(X)) + len(set(Y))) + '\n')


for _ in range(int(input())):
	n = int(input())
	x = set()
	y = set()
	for i in range(n):
		(x_i, y_i) = map(int, input().split())
		x.add(x_i)
		y.add(y_i)
	print(len(x) + len(y))


TC = int(input())
for T in range(TC):
	N = int(input())
	x = set()
	y = set()
	for i in range(N):
		(xi, yi) = map(int, input().split())
		x.add(xi)
		y.add(yi)
	print(len(x) + len(y))


T = int(input())
for _ in range(T):
	n = int(input())
	x1 = []
	y1 = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		x1.append(x)
		y1.append(y)
	print(len(set(x1)) + len(set(y1)))


for _ in range(int(input())):
	n = int(input())
	X = []
	Y = []
	for i in range(n):
		(x, y) = map(int, input().split())
		X.append(x)
		Y.append(y)
	print(len(set(X)) + len(set(Y)))


for _ in range(int(input())):
	(set_x, set_y) = (set(), set())
	for __ in range(int(input())):
		(a, b) = map(int, input().split())
		set_x.add(a)
		set_y.add(b)
	print(len(set_x) + len(set_y))


for i in range(int(input())):
	num = int(input())
	a = [j for k in range(num) for j in input().split()]
	x = set(a[::2])
	y = set(a[1::2])
	print(len(x) + len(y))


t = int(input())
for ni in range(t):
	n = int(input())
	(lv, lh) = (list(), list())
	count = 0
	for nj in range(n):
		(x, y) = map(int, input().split())
		vert = x
		hor = y
		lv.append(vert)
		lh.append(hor)
	print(len(set(lv)) + len(set(lh)))


for i in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l1.append(x)
		l2.append(y)
	print(len(list(set(l1))) + len(list(set(l2))))


for _ in range(int(input())):
	n = int(input())
	x = set()
	y = set()
	for i in range(n):
		(a, b) = map(int, input().split())
		x.add(a)
		y.add(b)
	print(len(x) + len(y))


for _ in range(int(input())):
	n = int(input())
	xset = set()
	yset = set()
	for i in range(n):
		(x, y) = map(int, input().split())
		xset.add(x)
		yset.add(y)
	print(len(xset) + len(yset))


for _ in range(int(input())):
	n = int(input())
	(x, y) = (set(), set())
	for i in range(n):
		inp = list(map(int, input().split()))
		x.add(inp[0])
		y.add(inp[1])
	print(len(x) + len(y))


for _ in range(int(input())):
	n = int(input())
	a = []
	o = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		o.append(y)
	print(len(set(a)) + len(set(o)))


for tc in range(int(input())):
	n = int(input())
	xlines = set(())
	ylines = set(())
	for i in range(n):
		(x, y) = map(int, input().split())
		xlines.add(x)
		ylines.add(y)
	print(len(xlines) + len(ylines))


t = int(input())
while t > 0:
	m = int(input())
	s = set()
	s1 = set()
	for z in range(m):
		(c, d) = map(int, input().split())
		s.add(c)
		s1.add(d)
	print(len(s) + len(s1))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	x = set({})
	y = set({})
	for _ in range(n):
		(xi, yi) = map(int, input().split())
		x.add(xi)
		y.add(yi)
	print(len(x) + len(y))


for _ in range(int(input())):
	N = int(input())
	hor = set()
	ver = set()
	for i in range(N):
		(x, y) = map(int, input().split())
		hor.add(x)
		ver.add(y)
	print(len(hor) + len(ver))


t = int(input())
for _ in range(t):
	n = int(input())
	d1 = {}
	d2 = {}
	for i in range(n):
		(i, j) = map(int, input().split())
		d1[i] = 1
		d2[j] = 1
	print(len(d1.keys()) + len(d2.keys()))


t = int(input())
while t != 0:
	n = int(input())
	setx = set()
	sety = set()
	lx = []
	ly = []
	for i in range(n):
		(a, b) = map(int, input().split())
		lx.append(a)
		ly.append(b)
	setx.update(lx)
	sety.update(ly)
	x = len(setx)
	y = len(sety)
	print(x + y)
	t = t - 1


for i in range(int(input())):
	N = int(input())
	X = []
	Y = []
	for i in range(N):
		(a, b) = map(int, input().split())
		X.append(a)
		Y.append(b)
	X = set(X)
	Y = set(Y)
	print(len(X) + len(Y))


t = int(input())
for i in range(t):
	n = int(input())
	xpoint = list()
	ypoint = list()
	for j in range(n):
		(x, y) = list(map(int, input().split(' ')))
		xpoint.append(x)
		ypoint.append(y)
	print(len(set(xpoint)) + len(set(ypoint)))


t = int(input())
for _ in range(t):
	n = int(input())
	lisx = []
	lisy = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		lisx.append(x)
		lisy.append(y)
	print(len(set(lisx)) + len(set(lisy)))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = set()
	list = []
	for i in range(n):
		(x, y) = map(int, input().split())
		temp = []
		temp.append(x)
		temp.append(y)
		list.append(temp)
	for i in range(n):
		a.add(list[i][0])
	count = len(a)
	a.clear()
	for i in range(n):
		a.add(list[i][1])
	count += len(a)
	print(count)


for _ in range(int(input())):
	n = int(input())
	(xs, ys) = (set(), set())
	for i in range(n):
		(x, y) = map(int, input().split())
		xs.add(x)
		ys.add(y)
	print(len(xs) + len(ys))


for _ in range(int(input())):
	point_set = []
	for _ in range(int(input())):
		point_set.append(list(map(int, input().split(' '))))
	(x, y) = list(zip(*point_set))
	print(len(set(x)) + len(set(y)))


for _ in range(int(input())):
	n = int(input())
	xl = []
	yl = []
	for i in range(n):
		(x, y) = map(int, input().split())
		xl += [x]
		yl += [y]
	total = len(set(xl)) + len(set(yl))
	print(total)


for j in range(int(input())):
	a = int(input())
	x = set()
	y = set()
	for i in range(a):
		(b, c) = map(int, input().split())
		x.add(b)
		y.add(c)
	s = len(x)
	p = len(y)
	print(s + p)


r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
mod = lambda n: n % (10 ** 9 + 7)
sl = lambda l: list(set(l))
soli = lambda : sorted(list(map(int, input().split())))
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : input()
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for i in range(int(input())):
	numOfPoints = ii()
	checkSet1 = set()
	checkSet2 = set()
	for i in range(numOfPoints):
		(coordX, coordY) = sepi()
		checkSet1.add(coordX)
		checkSet2.add(coordY)
	print(len(checkSet1) + len(checkSet2))


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = []
	list2 = []
	list3 = []
	for i in range(n):
		a = list(input().split())
		list1.append(a)
	for j in range(n):
		list2.append(list1[j][0])
		list3.append(list1[j][1])
	set2 = list(set(list2))
	set3 = list(set(list3))
	print(len(set2) + len(set3))


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l1 = []
	l2 = []
	for i in range(n):
		l1.append(l[i][0])
		l2.append(l[i][1])
	s1 = set(l1)
	s2 = set(l2)
	print(len(s1) + len(s2))


for _ in range(int(input())):
	n = int(input())
	lstx = []
	lsty = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		lstx.append(x)
		lsty.append(y)
	print(len(set(lstx)) + len(set(lsty)))


for _ in range(int(input())):
	n = int(input())
	ax = set()
	ay = set()
	for i in range(n):
		(x, y) = map(int, input().split())
		ax.add(x)
		ay.add(y)
	print(len(ax) + len(ay))


s = int(input())
for j in range(s):
	h = []
	v = []
	ans = 0
	n = int(input())
	for i in range(n):
		e = input().split()
		h.append(e[0])
		v.append(e[1])
		if e[0] == 1 and e[1] == 0:
			ans += 1
	h = list(set(h))
	v = list(set(v))
	ans = ans + len(h) + len(v)
	print(ans)


T = int(input())
for index in range(T):
	n = int(input())
	X = []
	Y = []
	for i in range(n):
		(x, y) = map(int, input().split())
		X.append(x)
		Y.append(y)
	d1 = dict()
	d2 = dict()
	for i in range(len(X)):
		d1[X[i]] = 1
	for i in range(len(Y)):
		d2[Y[i]] = 1
	print(len(d1) + len(d2))


t = int(input())
for i in range(t):
	x = int(input())
	a1 = []
	a2 = []
	for j in range(x):
		(a, b) = map(int, input().split())
		a1.append(a)
		a2.append(b)
	print(len(set(a1)) + len(set(a2)))


for t in range(int(input())):
	n = int(input())
	x = []
	y = []
	for i in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	print(len(set(x)) + len(set(y)))


t = input()
for c in range(0, int(t)):
	count = 0
	n = int(input())
	list1 = []
	list2 = []
	list3 = []
	list4 = []
	for i in range(n):
		(x, y) = input().split()
		o = int(x)
		m = int(y)
		list1.append(o)
		list2.append(m)
	list1 = set(list1)
	list2 = set(list2)
	print(len(list1) + len(list2))


for _ in range(int(input())):
	n = int(input())
	xl = []
	yl = []
	for i in range(n):
		(x, y) = map(int, input().split())
		xl.append(x)
		yl.append(y)
	a = len(set(xl))
	b = len(set(yl))
	print(a + b)


for _ in range(int(input())):
	n = int(input())
	l = []
	u = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		l.append(x)
		u.append(y)
	l = set(l)
	u = set(u)
	print(len(l) + len(u))


for tc in range(int(input())):
	c = []
	d = []
	e = []
	for i in range(int(input())):
		c.append(list(map(int, input().split())))
	for j in range(len(c)):
		d.append(c[j][0])
		e.append(c[j][1])
	print(len(set(d)) + len(set(e)))


t = int(input())
for _ in range(t):
	n = int(input())
	X = set()
	Y = set()
	count = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if x not in X:
			count += 1
			X.add(x)
		if y not in Y:
			count += 1
			Y.add(y)
	print(count)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	xx = []
	for _ in range(n):
		(x, y) = stdin.readline().strip().split()
		xx.append(x)
		xx.append(y)
	print(len(set(xx[::2])) + len(set(xx[1::2])))


for _ in range(int(input())):
	n = int(input())
	x1 = []
	y1 = []
	for i in range(n):
		(x, y) = map(int, input().split())
		x1.append(x)
		y1.append(y)
	a = len(set(x1))
	b = len(set(y1))
	print(a + b)


for t in range(int(input())):
	n = int(input())
	(x, y) = ([], [])
	for i in range(n):
		(x0, y0) = [int(j) for j in input().split()]
		x.append(x0)
		y.append(y0)
	ans = n * 2
	if len(x) - len(set(x)) > 0:
		ans = ans - len(x) + len(set(x))
	if len(y) - len(set(y)) > 0:
		ans = ans - len(y) + len(set(y))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lix = set()
	liy = set()
	for i in range(n):
		(xi, yi) = map(int, input().split())
		lix.add(xi)
		liy.add(yi)
	cnt = len(lix) + len(liy)
	print(cnt)


for i in range(int(input())):
	n = int(input())
	x = []
	y = []
	for a in range(n):
		(p, q) = map(int, input().split())
		x.append(p)
		y.append(q)
	k = set(x)
	l = set(y)
	print(len(list(k)) + len(list(l)))


for _ in range(int(input())):
	n = int(input())
	(l1, l2) = (set(), set())
	for i in range(n):
		(a, b) = map(int, input().split())
		l1.add(a)
		l2.add(b)
	print(len(l1) + len(l2))


for _ in range(int(input())):
	n = int(input())
	l = []
	m = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append(x)
		m.append(y)
	ans = len(set(l)) + len(set(m))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(xi, yi) = map(int, input().split())
		a.append(xi)
		b.append(yi)
	p = set(a)
	q = set(b)
	print(len(p) + len(q))


from collections import Counter
T = int(input())
for i in range(T):
	n = int(input())
	X = []
	Y = []
	for j in range(n):
		(x, y) = map(int, input().split())
		X.append(x)
		Y.append(y)
	distinct_x = len(Counter(X).keys())
	distinct_y = len(Counter(Y).keys())
	print(distinct_x + distinct_y)


t = int(input())
for i in range(t):
	n = int(input())
	s1 = set()
	s2 = set()
	for i in range(n):
		(x, y) = map(int, input().split())
		s1.add(x)
		s2.add(y)
	print(len(s1) + len(s2))


t = int(input())
for _ in range(t):
	n = int(input())
	xSet = set()
	ySet = set()
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		xSet.add(x)
		ySet.add(y)
	print(len(xSet) + len(ySet))


for _ in range(int(input())):
	n = int(input())
	h = set()
	k = set()
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		h.add(x)
		k.add(y)
	print(len(h) + len(k))


for i in range(int(input())):
	n = int(input())
	w1 = []
	w2 = []
	for y in range(n):
		(a, b) = map(int, input().split())
		w1.append(a)
		w2.append(b)
	r1 = set(w1)
	r2 = set(w2)
	sum = len(r1) + len(r2)
	print(sum)