compare.py

import sys


def shiftL(l, s):
	return l[s:] + l[:s]

def getDiff(li, totalLen):
	if len(li) < 2:
		raise Exception('toooo short')
	li.append(totalLen + li[0])
	nl = [li[i+1] - li[i] for i in range(len(li) - 1)]
	return nl

def genShiftIndex(l, s):
	sl = shiftL(l, s)
	s = set(sl)
	index = {i: [j for j in range(len(l)) if sl[j] == i] for i in s}
	index = {k: v for k,v in index.iteritems() if len(v) > 1}
	return index

def genShiftDiff(l, s):
	return {k: getDiff(v, len(l)) for k, v in genShiftIndex(l, s).iteritems()}

def genShiftdIndex(l, s):
	index = genShiftIndex(l, s)
	dindex = [v[0] for k,v in index.iteritems()]
	return sorted(dindex)

def genShiftdDiff(l, s):
	return getDiff(genShiftdIndex(l, s), len(l))

def comparedshift(l, a, b):
	if genShiftdDiff(l, a) < genShiftdDiff(l, b):
		return 'less'
	elif genShiftdDiff(l, a) > genShiftdDiff(l, b):
		return 'more'
	else:
		da = genShiftDiff(l, a)
		db = genShiftDiff(l, b)
		ia = genShiftdIndex(l, a)
		ib = genShiftdIndex(l, b)
		for i in range(len(ia)):
			va = shiftL(l, a)[ia[i]]
			vb = shiftL(l, b)[ib[i]]
			if da[va] < db[vb]:
				return 'less'
			elif da[va] > db[vb]:
				return 'more'
		return 'equal'

def genCode(l, i):
	if i == -1:
		return 'unique'
	di = genShiftdIndex(l, i)
	d = genShiftDiff(l, i)
	if len(di) == 1:
		return 'single' + str(d[shiftL(l, i)[di[0]]])
	dd = genShiftdDiff(l, i)
	string = 'multi' + str(dd)
	for pi in di:
		va = shiftL(l, i)[pi]
		string = string + str(d[va])
	return string

# def compareEqual(ca, cb):
# 	la, ia = ca
# 	lb, ib = cb
# 	if ia == -1 or ib == -1:
# 		if ia == -1 and ib == -1:
# 			return 'equal'
# 		return
# 	dia = genShiftdIndex(la, ia)
# 	dib = genShiftdIndex(lb, ib)
# 	da = genShiftDiff(la, ia)
# 	db = genShiftDiff(lb, ib)
# 	if len(dia) != len(dib):
# 		return
# 	if len(dia) == 0: # len(dib) == 0
# 		return 'equal'
# 	if len(dia) == 1: # len(dib) == 1
# 		va = shiftL(la, ia)[dia[0]]
# 		vb = shiftL(lb, ib)[dib[0]]
# 		if da[va] == db[vb]:
# 			return 'equal'
# 		return
# 	if genShiftdDiff(la, ia) == genShiftdDiff(lb, ib):
# 		for i in range(len(dia)):
# 			va = shiftL(la, ia)[dia[i]]
# 			vb = shiftL(lb, ib)[dib[i]]
# 			if da[va] != db[vb]:
# 				return
# 		return 'equal'

time = int(sys.stdin.readline())
for tt in range(time):
	n = int(sys.stdin.readline().split(' ')[0])
	code = []

	for t in range(n):
		l = map(int, sys.stdin.readline().split(' '))

		smallest = 0
		if len(genShiftdIndex(l, 0)) == 0:
			smallest = -1 # all unique
		elif len(genShiftdIndex(l, 0)) == 1:
			for i in range(1, len(l)):
				if genShiftdIndex(l, i)[0] == 0:
					if genShiftDiff(l, i)[shiftL(l, i)[0]] < genShiftDiff(l, smallest)[shiftL(l, smallest)[genShiftdIndex(l, smallest)[0]]]:
						smallest = i
		else:
			for i in range(1, len(l)):
				if genShiftdIndex(l, i)[0] == 0:
					result = comparedshift(l, smallest, i)
					if result == 'more':
						smallest = i
			#print smallest, shiftL(l, smallest)
		code.append(genCode(l, smallest))

	#print code
	#print set(map(genCode, code))
	print len(set(code))