Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

 
Example 1:
Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8). 

Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:
Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:
Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

 
Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Mathematics

Starter code: class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        

Solutions:
class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def triplets(nums1, nums2):
			sq = collections.Counter((x * x for x in nums1))
			num = collections.Counter(nums2)
			res = 0
			keys = sorted(num.keys())
			for (j, x) in enumerate(keys):
				if num[x] > 1 and x * x in sq:
					res += num[x] * (num[x] - 1) // 2 * sq[x * x]
				for y in keys[j + 1:]:
					if x * y in sq:
						res += num[x] * num[y] * sq[x * y]
			return res
		return triplets(nums1, nums2) + triplets(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = Counter(nums1)
		count2 = Counter(nums2)
		nums1 = sorted(count1.keys())
		nums2 = sorted(count2.keys())
		tot = 0
		for (c1, n1, c2, n2) in [(count1, nums1, count2, nums2), (count2, nums2, count1, nums1)]:
			for a in n1:
				s = a ** 2
				for b in n2:
					if b > a:
						break
					if s % b == 0 and s // b in c2:
						print((a, b))
						if b == a:
							if c2[b] >= 2:
								tot += c1[a] * comb(c2[b], 2)
						else:
							tot += c1[a] * c2[b] * c2[s // b]
		return tot


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def calc(a: List[int], b: List[int]):
			from collections import defaultdict
			freq = defaultdict(int)
			for ai in a:
				freq[ai] += 1
			_ans = 0
			for bi in b:
				t = bi * bi
				for k in freq:
					if t % k != 0 or t / k not in freq:
						continue
					elif t / k == k:
						_ans += freq[k] * (freq[k] - 1)
					else:
						_ans += freq[k] * freq[t / k]
			return int(_ans / 2)
		return calc(nums1, nums2) + calc(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		prod2 = collections.defaultdict(int)
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				prod = nums2[i] * nums2[j]
				if prod in prod2:
					prod2[prod] += 1
				else:
					prod2[prod] = 1
		res = 0
		for e in nums1:
			if e ** 2 in prod2:
				res += prod2[e ** 2]
		prod1 = collections.defaultdict(int)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				prod = nums1[i] * nums1[j]
				if prod in prod1:
					prod1[prod] += 1
				else:
					prod1[prod] = 1
		for e in nums2:
			if e * e in prod1:
				res += prod1[e * e]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ret = 0
		dict1 = defaultdict(int)
		dict2 = defaultdict(int)
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				dict2[nums2[j] * nums2[k]] += 1
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				dict1[nums1[j] * nums1[k]] += 1
		for i in range(len(nums1)):
			if nums1[i] ** 2 in dict2:
				ret += dict2[nums1[i] ** 2]
		for i in range(len(nums2)):
			if nums2[i] ** 2 in dict1:
				ret += dict1[nums2[i] ** 2]
		return ret


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(n1, n2) = (Counter([x * x for x in nums1]), Counter([x * x for x in nums2]))
		count = 0
		(l1, l2) = (len(nums1), len(nums2))
		for i in range(l2 - 1):
			for j in range(i + 1, l2):
				count += n1[nums2[i] * nums2[j]]
		for i in range(l1 - 1):
			for j in range(i + 1, l1):
				count += n2[nums1[i] * nums1[j]]
		return count


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find_triplets(nums_1, nums_2):
			ans = 0
			target = list(map(lambda x: x ** 2, nums_1))
			count = Counter(target)
			for j in range(len(nums_2)):
				for k in range(j + 1, len(nums_2)):
					if nums_2[j] * nums_2[k] in count:
						ans += count[nums_2[j] * nums_2[k]]
			return ans
		return find_triplets(nums1, nums2) + find_triplets(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = collections.defaultdict(int)
		d2 = collections.defaultdict(int)
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				d1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				d2[nums2[i] * nums2[j]] += 1
		c = 0
		for i in nums1:
			c += d2[i * i]
		for i in nums2:
			c += d1[i * i]
		print(d1, d2)
		return c


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(a, b):
			count = Counter((x ** 2 for x in a))
			return sum((count[x * y] for (x, y) in itertools.combinations(b, 2)))
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		l1 = len(nums1)
		l2 = len(nums2)
		upper1 = []
		upper2 = []
		for i in range(l1):
			for j in range(i + 1, l1):
				upper1.append(nums1[i] * nums1[j])
		for i in range(l2):
			for j in range(i + 1, l2):
				upper2.append(nums2[i] * nums2[j])
		Count_upper1 = collections.Counter(upper1)
		Count_upper2 = collections.Counter(upper2)
		count = 0
		for i in range(l1):
			count += Count_upper2[nums1[i] ** 2]
		for i in range(l2):
			count += Count_upper1[nums2[i] ** 2]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		target1 = {}
		target2 = {}
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				v = nums1[i] * nums1[j]
				if v in target1:
					target1[v] += 1
				else:
					target1[v] = 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				v = nums2[i] * nums2[j]
				if v in target2:
					target2[v] += 1
				else:
					target2[v] = 1
		answer = 0
		print(target1, target2)
		for num in nums1:
			if num * num in target2:
				answer += target2[num * num]
		for num in nums2:
			if num * num in target1:
				answer += target1[num * num]
		return answer


class Solution:

	def numTriplets(self, a1: List[int], a2: List[int]) -> int:
		(ans, m1, m2, n1, n2) = (0, Counter([x ** 2 for x in a1]), Counter([x ** 2 for x in a2]), len(a1), len(a2))
		for i in range(n1 - 1):
			for j in range(i + 1, n1):
				ans += m2[a1[i] * a1[j]]
		for i in range(n2 - 1):
			for j in range(i + 1, n2):
				ans += m1[a2[i] * a2[j]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		totalcount = 0
		nums1sq = defaultdict(int)
		for sq_val in [x * x for x in nums1]:
			nums1sq[sq_val] += 1
		nums2sq = defaultdict(int)
		for sq_val in [x * x for x in nums2]:
			nums2sq[sq_val] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				totalcount += nums1sq[nums2[i] * nums2[j]]
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				totalcount += nums2sq[nums1[i] * nums1[j]]
		return totalcount


from typing import List
from collections import Counter

class Solution:

	def numTriplets(self, en1: List[int], en2: List[int]) -> int:
		counter1 = Counter(en1)
		counter2 = Counter(en2)
		ct = 0
		for (ele1, ct1) in list(counter1.items()):
			tot = ele1 * ele1
			for ele2 in counter2:
				(div, mod) = divmod(tot, ele2)
				if mod != 0:
					continue
				if div in counter2:
					if ele2 == div:
						ct += ct1 * counter2[ele2] * (counter2[div] - 1)
					else:
						ct += ct1 * counter2[ele2] * counter2[div]
		for (ele1, ct1) in list(counter2.items()):
			tot = ele1 * ele1
			for ele2 in counter1:
				(div, mod) = divmod(tot, ele2)
				if mod != 0:
					continue
				if div in counter1:
					if ele2 == div:
						ct += ct1 * counter1[ele2] * (counter1[div] - 1)
					else:
						ct += ct1 * counter1[ele2] * counter1[div]
		return ct // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		n1 = collections.Counter([num ** 2 for num in nums1])
		cnt = 0
		for i in range(1, len(nums2)):
			for j in range(i):
				if nums2[i] * nums2[j] in n1:
					cnt += n1[nums2[i] * nums2[j]]
		n1 = collections.Counter([num ** 2 for num in nums2])
		for i in range(1, len(nums1)):
			for j in range(i):
				if nums1[i] * nums1[j] in n1:
					cnt += n1[nums1[i] * nums1[j]]
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		counter1 = Counter((num * num for num in nums1))
		counter2 = Counter((num * num for num in nums2))
		res = 0
		(n, m) = (len(nums1), len(nums2))
		for i in range(n - 1):
			for j in range(i + 1, n):
				curr = nums1[i] * nums1[j]
				res += counter2[curr]
		for i in range(m - 1):
			for j in range(i + 1, m):
				curr = nums2[i] * nums2[j]
				res += counter1[curr]
		return res


from collections import Counter

class Solution:

	def check_square(self, c, nums):
		tot = 0
		for j in range(len(nums)):
			for k in range(j + 1, len(nums)):
				tot += c[nums[j] * nums[k]]
		return tot

	def count_squares(self, nums):
		c = Counter([elem ** 2 for elem in nums])
		return c

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = self.count_squares(nums1)
		c2 = self.count_squares(nums2)
		sol1 = self.check_square(c1, nums2)
		sol2 = self.check_square(c2, nums1)
		return sol1 + sol2


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(n1_cnts, n2_cnts) = (Counter(nums1), Counter(nums2))
		good = 0
		for (n1, cnt) in list(n1_cnts.items()):
			n2_cnts_copy = n2_cnts.copy()
			for n2j in nums2:
				n2_cnts_copy[n2j] -= 1
				good += cnt * n2_cnts_copy[pow(n1, 2) / n2j]
		for (n2, cnt) in list(n2_cnts.items()):
			n1_cnts_copy = n1_cnts.copy()
			for n1j in nums1:
				n1_cnts_copy[n1j] -= 1
				good += cnt * n1_cnts_copy[pow(n2, 2) / n1j]
		return good


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = collections.Counter([i * i for i in nums1])
		c2 = collections.Counter([i * i for i in nums2])
		res = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				res += c2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				res += c1[nums2[i] * nums2[j]]
		return res


class Solution:

	def wrapper(self, toSquare, toProd):
		table = {}
		for integer in toSquare:
			squared = integer ** 2
			if squared not in table:
				table[squared] = 1
			else:
				table[squared] += 1
		counter = 0
		i = 0
		while i < len(toProd):
			j = i + 1
			while j < len(toProd):
				product = toProd[i] * toProd[j]
				if product in table:
					counter += table[product]
				j += 1
			i += 1
		return counter

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		counter = 0
		counter += self.wrapper(nums1, nums2)
		counter += self.wrapper(nums2, nums1)
		return counter


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		set1 = collections.Counter([x * x for x in nums1])
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				ans += set1[nums2[i] * nums2[j]]
		set2 = collections.Counter([x * x for x in nums2])
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				ans += set2[nums1[i] * nums1[j]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		import numpy as np
		l1 = len(nums1)
		l2 = len(nums2)
		upper1 = list(np.outer(np.array(nums1), np.array(nums1))[np.triu_indices(l1, 1)])
		upper2 = list(np.outer(np.array(nums2), np.array(nums2))[np.triu_indices(l2, 1)])
		Count_upper1 = collections.Counter(upper1)
		Count_upper2 = collections.Counter(upper2)
		count = 0
		for i in range(max(l1, l2)):
			if i < l1:
				count += Count_upper2[nums1[i] ** 2]
			if i < l2:
				count += Count_upper1[nums2[i] ** 2]
		return count


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		new1 = Counter(nums1)
		new2 = Counter(nums2)

		def helper(a, b):
			count = 0
			for key in a:
				target = key ** 2
				for kk in b:
					c = target // kk
					if c < kk:
						continue
					elif c == kk:
						count += b[kk] * (b[kk] - 1) * a[key] // 2
					elif target % kk == 0 and c in b:
						count += b[kk] * b[c] * a[key]
			return count
		return helper(new1, new2) + helper(new2, new1)


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		squares1 = Counter([x ** 2 for x in nums1])
		squares2 = Counter([x ** 2 for x in nums2])
		count = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in squares2:
					count = count + squares2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in squares1:
					count = count + squares1[nums2[i] * nums2[j]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sq_cnt1 = Counter([x * x for x in nums1])
		sq_cnt2 = Counter([x * x for x in nums2])
		count = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in sq_cnt2:
					count += sq_cnt2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in sq_cnt1:
					count += sq_cnt1[nums2[i] * nums2[j]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cal(lst1, lst2):
			count = 0
			d = {}
			for i in range(len(lst1)):
				v = lst1[i] * lst1[i]
				d[v] = d.get(v, 0) + 1
			for j in range(len(lst2)):
				for k in range(j + 1, len(lst2)):
					v = lst2[j] * lst2[k]
					if v in d:
						count += d[v]
			return count
		return cal(nums1, nums2) + cal(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		N1 = len(nums1)
		N2 = len(nums2)
		d1 = collections.defaultdict(int)
		for j in range(N1):
			for k in range(j + 1, N1):
				d1[nums1[j] * nums1[k]] += 1
		d2 = collections.defaultdict(int)
		for j in range(N2):
			for k in range(j + 1, N2):
				d2[nums2[j] * nums2[k]] += 1
		ans = 0
		for i in range(N1):
			ans += d2[nums1[i] * nums1[i]]
		for i in range(N2):
			ans += d1[nums2[i] * nums2[i]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = collections.Counter([x ** 2 for x in nums1])
		c2 = collections.Counter([y ** 2 for y in nums2])
		ans = 0
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				p = nums2[i] * nums2[j]
				ans += c1[p]
		for ii in range(len(nums1)):
			for jj in range(ii + 1, len(nums1)):
				p = nums1[ii] * nums1[jj]
				ans += c2[p]
		return ans


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		mp1 = defaultdict(int)
		mp2 = defaultdict(int)
		for n in nums1:
			mp1[n * n] += 1
		for n in nums2:
			mp2[n * n] += 1
		products1 = self.products(nums1)
		products2 = self.products(nums2)
		score = 0
		for p in products1:
			if mp2.get(p):
				score += mp2[p]
		for p in products2:
			if mp1.get(p):
				score += mp1[p]
		return score

	def products(self, nums):
		products = []
		n = len(nums)
		for i in range(0, n - 1):
			for m in nums[i + 1:]:
				products.append(nums[i] * m)
		return products


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		m = len(nums1)
		n = len(nums2)
		pairs1 = []
		pairs2 = []
		for i in range(n):
			for j in range(i + 1, n):
				pairs2.append(nums2[i] * nums2[j])
		for i in range(m):
			for j in range(i + 1, m):
				pairs1.append(nums1[i] * nums1[j])
		pairs1.sort()
		pairs2.sort()
		if len(pairs1) == 0 or len(pairs2) == 0:
			return 0

		def bs1(arr, key):
			if arr[0] > key:
				return -1
			if arr[-1] < key:
				return -1
			lo = 0
			hi = len(arr) - 1
			left = -1
			while lo <= hi:
				mid = (lo + hi) // 2
				if arr[mid] < key:
					lo = mid + 1
				elif arr[mid] == key:
					left = mid
					hi = mid - 1
				else:
					hi = mid - 1
			return left

		def bs2(arr, key):
			if arr[0] > key:
				return -1
			if arr[-1] < key:
				return -1
			lo = 0
			hi = len(arr) - 1
			right = -1
			while lo <= hi:
				mid = (lo + hi) // 2
				if arr[mid] < key:
					lo = mid + 1
				elif arr[mid] == key:
					right = mid
					lo = mid + 1
				else:
					hi = mid - 1
			return right
		ans = 0
		for i in nums1:
			sq = i * i
			left = bs1(pairs2, sq)
			right = bs2(pairs2, sq)
			if left == -1:
				continue
			ans += right - left + 1
		for i in nums2:
			sq = i * i
			left = bs1(pairs1, sq)
			right = bs2(pairs1, sq)
			if left == -1:
				continue
			ans += right - left + 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		dict1 = {}
		dict2 = {}
		for i in nums1:
			x = i * i
			if x not in dict1.keys():
				dict1[x] = 1
			else:
				dict1[x] = dict1[x] + 1
		for j in nums2:
			x = j * j
			if x not in dict2.keys():
				dict2[x] = 1
			else:
				dict2[x] = dict2[x] + 1
		print(dict1)
		print(dict2)
		for j in range(0, len(nums2)):
			for k in range(j + 1, len(nums2)):
				if nums2[k] * nums2[j] in dict1.keys():
					count = count + dict1[nums2[j] * nums2[k]]
		for j in range(0, len(nums1)):
			for k in range(j + 1, len(nums1)):
				if nums1[j] * nums1[k] in dict2.keys():
					count = count + dict2[nums1[j] * nums1[k]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def getRoots(nums):
			prods = []
			for (i, j) in itertools.combinations(nums, 2):
				prods.append(i * j)
			return prods

		def ways(nums1, nums2):
			ans = 0
			square = collections.Counter([n ** 2 for n in nums1])
			prods = getRoots(nums2)
			for p in prods:
				ans += square[p]
			return ans
		return ways(nums1, nums2) + ways(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def typeone(n1, n2):
			L1 = len(n1)
			L2 = len(n2)
			dic = {}
			count = 0
			for j in range(L2 - 1):
				for k in range(j + 1, L2):
					if n2[j] * n2[k] not in dic:
						dic[n2[j] * n2[k]] = 1
					else:
						dic[n2[j] * n2[k]] += 1
			for u in n1:
				if u * u in dic:
					count += dic[u * u]
			return count
		return typeone(nums1, nums2) + typeone(nums2, nums1)


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		t1 = defaultdict(int)
		t2 = defaultdict(int)
		ans = 0
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				t1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				t2[nums2[i] * nums2[j]] += 1
		for n in nums1:
			ans += t2[n * n]
		for n in nums2:
			ans += t1[n * n]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from math import sqrt
		from collections import Counter

		def find(target, pool):
			ans = 0
			target = Counter(target)
			for i in range(0, len(pool) - 1):
				for j in range(i + 1, len(pool)):
					ans += target.get(sqrt(pool[i] * pool[j]), 0)
			return ans
		return find(nums1, nums2) + find(nums2, nums1)


def func(xs, ys):
	sqs = [x ** 2 for x in xs]
	seen = collections.defaultdict(int)
	res = 0
	for y in ys:
		for x in sqs:
			if x % y == 0:
				res += seen[x // y]
		seen[y] += 1
	return res

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return func(nums1, nums2) + func(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		dic1 = {}
		dic2 = {}
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				v = nums1[i] * nums1[j]
				if dic1.get(v) is None:
					dic1[v] = 1
				else:
					dic1[v] = dic1[v] + 1
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				v = nums2[i] * nums2[j]
				if dic2.get(v) is None:
					dic2[v] = 1
				else:
					dic2[v] = dic2[v] + 1
		cnt = 0
		for v in nums1:
			if dic2.get(v * v):
				cnt += dic2.get(v * v)
		for v in nums2:
			if dic1.get(v * v):
				cnt += dic1.get(v * v)
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = [x * x for x in nums1]
		n2 = [x * x for x in nums2]
		dnum1 = collections.Counter(n1)
		dnum2 = collections.Counter(n2)
		ans = 0
		nums1.sort()
		nums2.sort()
		m1 = max(dnum1.keys())
		m2 = max(dnum2.keys())
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				comb = nums1[i] * nums1[j]
				if comb in dnum2:
					ans += dnum2[nums1[i] * nums1[j]]
				if comb > m2:
					break
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				comb = nums2[i] * nums2[j]
				if comb in dnum1:
					ans += dnum1[nums2[i] * nums2[j]]
				if comb > m1:
					break
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		Type1 = dict()
		Product1 = dict()
		Type2 = dict()
		Product2 = dict()
		for i in range(len(nums1)):
			product = nums1[i] * nums1[i]
			if product in Product1.keys():
				Product1[product] += 1
			else:
				Product1[product] = 1
			for j in range(i + 1, len(nums1)):
				new_product = nums1[i] * nums1[j]
				if new_product in Type1.keys():
					Type1[new_product] += 1
				else:
					Type1[new_product] = 1
		for i in range(len(nums2)):
			product = nums2[i] * nums2[i]
			if product in Product2.keys():
				Product2[product] += 1
			else:
				Product2[product] = 1
			for j in range(i + 1, len(nums2)):
				new_product = nums2[i] * nums2[j]
				if new_product in Type2.keys():
					Type2[new_product] += 1
				else:
					Type2[new_product] = 1
		res = 0
		for i in Product1.keys():
			if i in Type2.keys():
				res += Product1[i] * Type2[i]
		for i in Product2.keys():
			if i in Type1.keys():
				res += Product2[i] * Type1[i]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		map1 = {}
		map2 = {}
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				prod = nums1[i] * nums1[j]
				map1.setdefault(prod, 0)
				map1[prod] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				prod = nums2[i] * nums2[j]
				map2.setdefault(prod, 0)
				map2[prod] += 1
		res = 0
		for num in nums1:
			if num ** 2 in map2:
				res += map2[num ** 2]
		for num in nums2:
			if num ** 2 in map1:
				res += map1[num ** 2]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		products1 = collections.defaultdict(int)
		products2 = collections.defaultdict(int)
		result = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				p = nums1[i] * nums1[j]
				products1[p] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				p = nums2[i] * nums2[j]
				products2[p] += 1
		for num in nums1:
			result += products2[num * num]
		for num in nums2:
			result += products1[num * num]
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = self.findTriple(nums1, nums2)
		count += self.findTriple(nums2, nums1)
		return count

	def findTriple(self, nums1, nums2):
		counts = {}
		for num in nums2:
			if num not in counts:
				counts[num] = 0
			counts[num] += 1
		tcount = 0
		for i in range(0, len(nums1)):
			for j in range(0, len(nums2)):
				if nums2[j] < nums1[i] and nums1[i] * nums1[i] % nums2[j] == 0 and (nums1[i] * nums1[i] // nums2[j] in counts):
					tcount += counts[nums1[i] * nums1[i] // nums2[j]]
			if nums1[i] in counts:
				tcount += counts[nums1[i]] * (counts[nums1[i]] - 1) // 2
		return tcount


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		hash1 = defaultdict(int)
		hash2 = defaultdict(int)
		count = 0
		for i in nums1:
			hash1[i * i] += 1
		for i in nums2:
			hash2[i * i] += 1
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in hash2:
					count += hash2[nums1[i] * nums1[j]]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in hash1:
					count += hash1[nums2[i] * nums2[j]]
		return count


class Solution:

	def numTriplets(self, a: List[int], b: List[int]) -> int:

		def count(a, b):
			c = Counter()
			for (x, y) in combinations(b, 2):
				c[x * y] += 1
			ret = 0
			for x in a:
				ret += c[x * x]
			return ret
		return count(a, b) + count(b, a)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProd(n1, n2):
			d = Counter()
			for (i, a) in enumerate(n1):
				for j in range(i + 1, len(n1)):
					d[a * n1[j]] += 1
			return sum((d[i * i] for i in n2))
		return twoProd(nums1, nums2) + twoProd(nums2, nums1)


class Solution:

	def wrapper(self, toSquare, toProd):
		table = {}
		for integer in toSquare:
			squared = integer ** 2
			if squared not in table:
				table[squared] = 1
			else:
				table[squared] += 1
		counter = 0
		i = 0
		while i < len(toProd):
			j = i + 1
			while j < len(toProd):
				product = toProd[i] * toProd[j]
				if product in table:
					counter += table[product]
				j += 1
			i += 1
		return counter

	def numTriplets1(self, nums1: List[int], nums2: List[int]) -> int:
		counter = 0
		counter += self.wrapper(nums1, nums2)
		counter += self.wrapper(nums2, nums1)
		return counter

	def get_tables(self, nums):
		squares = {}
		products = {}
		i = 0
		while i != len(nums):
			j = i
			while j != len(nums):
				product_or_square = nums[i] * nums[j]
				if i == j:
					if product_or_square not in squares:
						squares[product_or_square] = 1
					else:
						squares[product_or_square] += 1
				elif product_or_square not in products:
					products[product_or_square] = 1
				else:
					products[product_or_square] += 1
				j += 1
			i += 1
		return (products, squares)

	def get_counts(self, products, squares):
		counter = 0
		if len(products) > len(squares):
			for square in squares:
				if square in products:
					counter += squares[square] * products[square]
		else:
			for product in products:
				if product in squares:
					counter += products[product] * squares[product]
		return counter

	def numTriplets2(self, nums1: List[int], nums2: List[int]) -> int:
		(products1, squares1) = self.get_tables(nums1)
		(products2, squares2) = self.get_tables(nums2)
		counter = 0
		counter += self.get_counts(products1, squares2)
		counter += self.get_counts(products2, squares1)
		return counter

	def get_products(self, nums):
		table = {}
		i = 0
		while i < len(nums) - 1:
			j = i + 1
			while j < len(nums):
				prod = nums[i] * nums[j]
				if prod not in table:
					table[prod] = 1
				else:
					table[prod] += 1
				j += 1
			i += 1
		return table

	def check_squares_in_prods(self, nums, prods):
		counter = 0
		for i in nums:
			sq = i ** 2
			if sq in prods:
				counter += prods[sq]
		return counter

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		prods1 = self.get_products(nums1)
		prods2 = self.get_products(nums2)
		counter = 0
		counter += self.check_squares_in_prods(nums1, prods2)
		counter += self.check_squares_in_prods(nums2, prods1)
		return counter


class Solution:

	def helper(self, nums1, nums2):
		n1 = len(nums1)
		n2 = len(nums2)
		ans = 0
		h1 = {}
		for j in range(n1):
			for k in range(j + 1, n1):
				if nums1[j] * nums1[k] not in h1:
					h1[nums1[j] * nums1[k]] = 1
				else:
					h1[nums1[j] * nums1[k]] += 1
		l = [i ** 2 for i in nums2]
		ans = 0
		for i in l:
			if i in h1:
				ans += h1[i]
		return ans

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.helper(nums1, nums2) + self.helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def multi(arr):
			D = {}
			for i in range(len(arr)):
				for j in range(i + 1, len(arr)):
					if arr[i] * arr[j] not in D:
						D[arr[i] * arr[j]] = 1
					else:
						D[arr[i] * arr[j]] += 1
			return D
		nums1_multi = multi(nums1)
		nums2_multi = multi(nums2)
		res = 0
		for i in nums1:
			res += nums2_multi.get(i ** 2, 0)
		for i in nums2:
			res += nums1_multi.get(i ** 2, 0)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		num1_counts = collections.Counter(nums1)
		num2_counts = collections.Counter(nums2)
		res = 0

		def findMatches(d1, d2):
			res = 0
			for n1 in d1:
				square = n1 * n1
				checked = set()
				for n2 in d2:
					if n2 in checked or square % n2:
						continue
					k = square // n2
					if k == n2:
						res += d1[n1] * d2[n2] * (d2[n2] - 1) // 2
					elif k in d2:
						res += d1[n1] * d2[n2] * d2[k]
						checked.add(k)
					checked.add(n2)
			return res
		return findMatches(num1_counts, num2_counts) + findMatches(num2_counts, num1_counts)


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:
		countA = defaultdict(int)
		countB = defaultdict(int)
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				countA[A[i] * A[j]] += 1
		for i in range(len(B)):
			for j in range(i + 1, len(B)):
				countB[B[i] * B[j]] += 1
		res = 0
		for i in range(len(A)):
			val = A[i] ** 2
			res += countB[val]
		for i in range(len(B)):
			val = B[i] ** 2
			res += countA[val]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def findTriplet2(arr1, arr2):
			result = 0
			m = len(arr2)
			count = collections.Counter([x ** 2 for x in arr1])
			for j in range(m):
				for k in range(j + 1, m):
					if arr2[j] * arr2[k] in list(count.keys()):
						result += count[arr2[j] * arr2[k]]
			return result

		def findTriplet(arr1, arr2):
			(n, m) = (len(arr1), len(arr2))
			triplets = 0
			for i in range(n):
				for j in range(m):
					for k in range(j + 1, m):
						if arr1[i] ** 2 == arr2[j] * arr2[k]:
							triplets += 1
			return triplets
		return findTriplet2(nums1, nums2) + findTriplet2(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def numValid(target, nums):
			(start, end) = (0, len(nums) - 1)
			ans = 0
			while start < end:
				if target * target == nums[start] * nums[end]:
					if nums[start] == nums[end]:
						n = end - start + 1
						ans += n * (n - 1) // 2
						break
					else:
						start += 1
						end -= 1
						dup1 = dup2 = 1
						while start < end and nums[start - 1] == nums[start]:
							start += 1
							dup1 += 1
						start -= 1
						while start < end and nums[end] == nums[end + 1]:
							end -= 1
							dup2 += 1
						ans += dup1 * dup2
				elif target * target < nums[start] * nums[end]:
					end -= 1
				elif target * target > nums[start] * nums[end]:
					start += 1
			return ans
		ans = 0
		for num1 in nums1:
			ans += numValid(num1, nums2)
		for num2 in nums2:
			ans += numValid(num2, nums1)
		return ans


class Solution(object):

	def numTriplets(self, A, B):
		from collections import Counter
		countA = Counter()
		countB = Counter()
		for (i, x) in enumerate(A):
			for j in range(i + 1, len(A)):
				y = A[j]
				countA[x * y] += 1
		for (i, x) in enumerate(B):
			for j in range(i + 1, len(B)):
				y = B[j]
				countB[x * y] += 1
		ans = 0
		for (i, x) in enumerate(A):
			ans += countB[x * x]
		for (i, x) in enumerate(B):
			ans += countA[x * x]
		return ans


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:
		countA = Counter()
		countB = Counter()
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				countA[A[i] * A[j]] += 1
		for i in range(len(B)):
			for j in range(i + 1, len(B)):
				countB[B[i] * B[j]] += 1
		ans = 0
		for x in A:
			ans += countB[x * x]
		for x in B:
			ans += countA[x * x]
		return ans


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sqr_num1 = Counter((x ** 2 for x in nums1))
		sqr_num2 = Counter((x ** 2 for x in nums2))
		(len_num1, len_num2) = (len(nums1), len(nums2))
		(multi_num1, multi_num2) = (Counter(), Counter())
		if len_num1 > 1:
			for i in range(len_num1 - 1):
				for j in range(i + 1, len_num1):
					multi_num1[nums1[i] * nums1[j]] += 1
		if len_num2 > 1:
			for i in range(len_num2 - 1):
				for j in range(i + 1, len_num2):
					multi_num2[nums2[i] * nums2[j]] += 1
		res = 0
		for n in sqr_num1:
			if n in multi_num2:
				res += sqr_num1[n] * multi_num2[n]
		for n in sqr_num2:
			if n in multi_num1:
				res += sqr_num2[n] * multi_num1[n]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def check(A, B):
			(n, res) = (len(B), 0)
			C = Counter(map(lambda i: i * i, A))
			for i in range(n):
				for j in range(i + 1, n):
					res += C[B[i] * B[j]]
			return res
		return check(nums1, nums2) + check(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def h(nums1, nums2):
			n = len(nums1)
			counter = collections.Counter()
			for i in range(n):
				for j in range(i + 1, n):
					counter[nums1[i] * nums1[j]] += 1
			return sum((counter[i ** 2] for i in nums2))
		return h(nums1, nums2) + h(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def get_sqs(nums):
			c = collections.Counter()
			for j in range(len(nums)):
				for k in range(j + 1, len(nums)):
					c[nums[j] * nums[k]] += 1
			return c
		sq1s = get_sqs(nums1)
		sq2s = get_sqs(nums2)
		res = 0
		for n in nums1:
			res += sq2s[n * n]
		for n in nums2:
			res += sq1s[n * n]
		return res


class Solution:

	def build_triplets(self, numbers1, numbers2):
		ret = 0
		for (number1, occurrences1) in numbers1.items():
			number1 *= number1
			checked_numbers = set()
			for (number2, occurrences2) in numbers2.items():
				if number2 not in checked_numbers:
					required = number1 // number2
					if required not in checked_numbers and required * number2 == number1 and (required in numbers2):
						if required == number2:
							ret += occurrences2 * occurrences1 * (occurrences1 - 1) // 2
						else:
							ret += occurrences2 * numbers2[required] * occurrences1
						checked_numbers.add(required)
		return ret

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		numbers1 = collections.Counter(nums1)
		numbers2 = collections.Counter(nums2)
		return self.build_triplets(numbers1, numbers2) + self.build_triplets(numbers2, numbers1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n = len(nums1)
		m = len(nums2)
		nums2_pairs = Counter()
		nums1_pairs = Counter()
		for i in range(n):
			for j in range(i + 1, n):
				nums1_pairs[nums1[i] * nums1[j]] += 1
		for i in range(m):
			for j in range(i + 1, m):
				nums2_pairs[nums2[i] * nums2[j]] += 1
		ans = 0
		for i in range(n):
			ans += nums2_pairs[nums1[i] * nums1[i]]
		for i in range(m):
			ans += nums1_pairs[nums2[i] * nums2[i]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(a, b):
			ans = 0
			hashm = {}
			for i in a:
				if i * i not in hashm:
					hashm[i * i] = 1
				else:
					hashm[i * i] = hashm[i * i] + 1
			for i in range(len(b)):
				for j in range(i + 1, len(b)):
					if b[i] * b[j] in hashm:
						ans = ans + hashm[b[i] * b[j]]
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(mul1, mul2) = (Counter(), Counter())
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				mul1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				mul2[nums2[i] * nums2[j]] += 1
		tots = 0
		for i in range(len(nums1)):
			tots += mul2[nums1[i] ** 2]
		for i in range(len(nums2)):
			tots += mul1[nums2[i] ** 2]
		return tots


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:

		def getTriplets(A, B):
			(m, n) = (len(A), len(B))
			ans = 0
			counter = Counter()
			for j in range(n):
				for k in range(j + 1, n):
					prod = B[j] * B[k]
					counter[prod] += 1
			for i in range(m):
				prod = A[i] ** 2
				ans += counter[prod]
			return ans
		return getTriplets(A, B) + getTriplets(B, A)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		rep = 0
		rep += self.getNumTriplets(nums1, nums2)
		rep += self.getNumTriplets(nums2, nums1)
		return rep

	def getNumTriplets(self, nums1, nums2):
		num1 = [n ** 2 for n in nums1]
		num2 = []
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				num2.append(nums2[i] * nums2[j])
		num2.sort()
		num1.sort()
		rep = 0
		k = 0
		while k < len(num1):
			cur = self.exist(num2, num1[k])
			rep += cur
			while k + 1 < len(num1) and num1[k + 1] == num1[k]:
				rep += cur
				k += 1
			k += 1
		return rep

	def exist(self, nums, target):
		l = 0
		r = len(nums) - 1
		while l <= r:
			mid = l + (r - l) // 2
			if nums[mid] > target:
				r = mid - 1
			elif nums[mid] < target:
				l = mid + 1
			else:
				l = self.leftSearch(nums[:mid + 1], target)
				r = self.rightSearch(nums[mid:], target) + mid
				return r - l + 1
		return 0

	def leftSearch(self, nums, target):
		(l, r) = (0, len(nums) - 1)
		while l <= r:
			mid = l + (r - l) // 2
			if nums[mid] == target:
				r = mid - 1
			else:
				l = mid + 1
		return l

	def rightSearch(self, nums, target):
		(l, r) = (0, len(nums) - 1)
		while l <= r:
			mid = l + (r - l) // 2
			if nums[mid] == target:
				l = mid + 1
			else:
				r = mid - 1
		return r


class Solution:

	def wrapper(self, toSquare, toProd):
		table = {}
		for integer in toSquare:
			squared = integer ** 2
			if squared not in table:
				table[squared] = 1
			else:
				table[squared] += 1
		counter = 0
		i = 0
		while i < len(toProd):
			j = i + 1
			while j < len(toProd):
				product = toProd[i] * toProd[j]
				if product in table:
					counter += table[product]
				j += 1
			i += 1
		return counter

	def numTriplets1(self, nums1: List[int], nums2: List[int]) -> int:
		counter = 0
		counter += self.wrapper(nums1, nums2)
		counter += self.wrapper(nums2, nums1)
		return counter

	def get_tables(self, nums):
		squares = {}
		products = {}
		i = 0
		while i != len(nums):
			j = i
			while j != len(nums):
				product_or_square = nums[i] * nums[j]
				if i == j:
					if product_or_square not in squares:
						squares[product_or_square] = 1
					else:
						squares[product_or_square] += 1
				elif product_or_square not in products:
					products[product_or_square] = 1
				else:
					products[product_or_square] += 1
				j += 1
			i += 1
		return (products, squares)

	def get_counts(self, products, squares):
		counter = 0
		if len(products) > len(squares):
			for square in squares:
				if square in products:
					counter += squares[square] * products[square]
		else:
			for product in products:
				if product in squares:
					counter += products[product] * squares[product]
		return counter

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(products1, squares1) = self.get_tables(nums1)
		(products2, squares2) = self.get_tables(nums2)
		counter = 0
		counter += self.get_counts(products1, squares2)
		counter += self.get_counts(products2, squares1)
		return counter


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import Counter
		(m, n) = (len(nums1), len(nums2))
		res = 0
		pool2 = Counter()
		for i in range(n - 1):
			for j in range(i + 1, n):
				curr = nums2[i] * nums2[j]
				pool2[curr] += 1
		for v in nums1:
			curr = v ** 2
			if curr in pool2:
				res += pool2[curr]
		pool1 = Counter()
		for i in range(m - 1):
			for j in range(i + 1, m):
				curr = nums1[i] * nums1[j]
				pool1[curr] += 1
		for v in nums2:
			curr = v ** 2
			if curr in pool1:
				res += pool1[curr]
		return res


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(A, B):
			ans = 0
			C = Counter([a * a for a in A])
			D = Counter()
			for b in B:
				for (k, v) in D.items():
					if k * b in C:
						ans += v * C[k * b]
				D[b] += 1
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


import math

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		cnt = 0
		d = {}
		ans = 0
		for i in range(0, len(nums2)):
			for j in range(i + 1, len(nums2)):
				if i != j:
					p = nums2[i] * nums2[j]
					try:
						d[p] += 1
					except:
						d[p] = 1
		for i in range(0, len(nums1)):
			p = nums1[i] * nums1[i]
			try:
				if d[p] > 0:
					cnt = cnt + d[p]
			except:
				ans = 1
		d = {}
		for i in range(0, len(nums1)):
			for j in range(i + 1, len(nums1)):
				if i != j:
					p = nums1[i] * nums1[j]
					try:
						d[p] += 1
					except:
						d[p] = 1
		for i in range(0, len(nums2)):
			p = nums2[i] * nums2[i]
			try:
				if d[p] > 0:
					cnt = cnt + d[p]
			except:
				ans = 1
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n = len(nums1)
		m = len(nums2)
		n2dict = defaultdict(int)
		m2dict = defaultdict(int)
		for x in nums1:
			n2dict[x * x] += 1
		for x in nums2:
			m2dict[x * x] += 1
		out = 0
		for i in range(m):
			for j in range(i + 1, m):
				key = nums2[i] * nums2[j]
				if nums2[i] * nums2[j] in n2dict:
					out += n2dict[key]
		for i in range(n):
			for j in range(i + 1, n):
				key = nums1[i] * nums1[j]
				if key in m2dict:
					out += m2dict[key]
		return out


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		h1 = defaultdict(list)
		h2 = defaultdict(list)
		n = len(nums1)
		m = len(nums2)
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				h1[nums1[i] * nums1[j]].append((i, j))
		for i in range(m):
			for j in range(i + 1, m):
				h2[nums2[i] * nums2[j]].append((i, j))
		for i in range(n):
			if nums1[i] ** 2 in h2:
				ans += len(h2[nums1[i] ** 2])
		for i in range(m):
			if nums2[i] ** 2 in h1:
				ans += len(h1[nums2[i] ** 2])
		return ans


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		output = 0
		sq1 = Counter(map(lambda q: q * q, nums1))
		sq2 = Counter(map(lambda q: q * q, nums2))
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				output += sq1[nums2[i] * nums2[j]]
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				output += sq2[nums1[i] * nums1[j]]
		return output


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(d1, d2) = (dict(), dict())
		for (idx, n1) in enumerate(nums1):
			d1[idx] = dict()
			for elm in nums1[idx + 1:]:
				try:
					d1[idx][elm] += 1
				except KeyError:
					d1[idx][elm] = 1
		for (idx, n2) in enumerate(nums2):
			d2[idx] = dict()
			for elm in nums2[idx + 1:]:
				try:
					d2[idx][elm] += 1
				except KeyError:
					d2[idx][elm] = 1
		good_dict = {}
		for n1 in nums1:
			if (1, n1) not in good_dict:
				good = 0
				for (idx, n2) in enumerate(nums2):
					try:
						good += d2[idx][n1 ** 2 / n2]
					except KeyError:
						pass
				good_dict[1, n1] = [good, 1]
			else:
				good_dict[1, n1][-1] += 1
		for n2 in nums2:
			if (2, n2) not in good_dict:
				good = 0
				for (idx, n1) in enumerate(nums1):
					try:
						good += d1[idx][n2 ** 2 / n1]
					except KeyError:
						pass
				good_dict[2, n2] = [good, 1]
			else:
				good_dict[2, n2][-1] += 1
		return sum((val * q for (val, q) in list(good_dict.values())))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def fun(arr):
			res = {}
			for i in range(len(arr) - 1):
				for j in range(i + 1, len(arr)):
					if arr[i] * arr[j] in res.keys():
						res[arr[i] * arr[j]] += 1
					else:
						res[arr[i] * arr[j]] = 1
			return res
		x = fun(nums1)
		y = fun(nums2)
		res = 0
		for i in range(len(nums1)):
			if nums1[i] ** 2 in y.keys():
				print(nums1[i])
				res += y[nums1[i] ** 2]
		for i in range(len(nums2)):
			if nums2[i] ** 2 in x.keys():
				res += x[nums2[i] ** 2]
		return res


import itertools

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		dicA = {}
		dicB = {}
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in dicA:
					dicA[nums1[i] * nums1[j]] += 1
				else:
					dicA[nums1[i] * nums1[j]] = 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in dicB:
					dicB[nums2[i] * nums2[j]] += 1
				else:
					dicB[nums2[i] * nums2[j]] = 1
		ans = 0
		for i in range(len(nums1)):
			try:
				val = dicB[nums1[i] * nums1[i]]
				ans += val
			except KeyError:
				pass
		for i in range(len(nums2)):
			try:
				val = dicA[nums2[i] * nums2[i]]
				ans += val
			except KeyError:
				pass
		return ans


import collections

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		counts1 = collections.Counter(nums1)
		counts2 = collections.Counter(nums2)
		print(counts1)
		print(counts2)

		def doit(c1, c2):
			total = 0
			for k1 in c1:
				for k2 in c2:
					neededK = k1 * k1 / k2
					if neededK == int(neededK):
						neededK = int(neededK)
						if k2 == neededK:
							i = c2[neededK]
							j = (i - 1 + 1) * (i - 1) // 2
							total += c1[k1] * j
						elif k2 < neededK:
							total += c1[k1] * c2[k2] * c2[neededK]
						print(k1, k2, neededK, total)
			return total
		return doit(counts1, counts2) + doit(counts2, counts1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(lookup1, lookup2, res) = ({}, {}, 0)
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in lookup1:
					lookup1[nums1[i] * nums1[j]] += 1
				else:
					lookup1[nums1[i] * nums1[j]] = 1
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in lookup2:
					lookup2[nums2[i] * nums2[j]] += 1
				else:
					lookup2[nums2[i] * nums2[j]] = 1
		for i in nums1:
			if i * i in lookup2:
				res += lookup2[i * i]
		for i in nums2:
			if i * i in lookup1:
				res += lookup1[i * i]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		n1 = len(nums1)
		n2 = len(nums2)
		nums1_product = defaultdict(int)
		nums2_product = defaultdict(int)
		for i in range(n1 - 1):
			for j in range(i + 1, n1):
				nums1_product[nums1[i] * nums1[j]] += 1
		for i in range(n2 - 1):
			for j in range(i + 1, n2):
				nums2_product[nums2[i] * nums2[j]] += 1
		for num1 in nums1:
			target = num1 ** 2
			ans += nums2_product[target]
		for num2 in nums2:
			target = num2 ** 2
			ans += nums1_product[target]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(lookup1, lookup2) = (collections.defaultdict(int), collections.defaultdict(int))
		for n in nums1:
			lookup1[n] += 1
		for n in nums2:
			lookup2[n] += 1
		res = 0
		for k in [0, 1]:
			nums = nums1 if not k else nums2
			lookup = lookup1 if k else lookup2
			for i in range(len(nums)):
				for j in range(i + 1, len(nums)):
					prod = nums[i] * nums[j]
					k = int(math.sqrt(prod))
					if k * k == prod and k in lookup:
						res += lookup[k]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ct = 0
		d = {}
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				if nums2[j] * nums2[k] in d:
					d[nums2[j] * nums2[k]] = d[nums2[j] * nums2[k]] + 1
				else:
					d[nums2[j] * nums2[k]] = 1
		dd = {}
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				if nums1[j] * nums1[k] in dd:
					dd[nums1[j] * nums1[k]] = dd[nums1[j] * nums1[k]] + 1
				else:
					dd[nums1[j] * nums1[k]] = 1
		ct = 0
		for i in range(len(nums1)):
			x = nums1[i] * nums1[i]
			if x in d:
				ct = ct + d[x]
		for i in range(len(nums2)):
			x = nums2[i] * nums2[i]
			if x in dd:
				ct = ct + dd[x]
		return ct


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(m1_square, m2_square) = ({}, {})
		for x in nums1:
			x_square = x ** 2
			m1_square[x_square] = m1_square.get(x_square, 0) + 1
		for x in nums2:
			x_square = x ** 2
			m2_square[x_square] = m2_square.get(x_square, 0) + 1
		(m, n) = (len(nums1), len(nums2))
		ans = 0
		for j in range(m - 1):
			for k in range(j + 1, m):
				if nums1[j] * nums1[k] in m2_square:
					ans += m2_square[nums1[j] * nums1[k]]
		for j in range(n - 1):
			for k in range(j + 1, n):
				if nums2[j] * nums2[k] in m1_square:
					ans += m1_square[nums2[j] * nums2[k]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		m1 = collections.defaultdict(int)
		m2 = collections.defaultdict(int)
		for (i, num) in enumerate(nums1):
			m1[num] += 1
		for (i, num) in enumerate(nums2):
			m2[num] += 1
		self.ans = 0

		def count(nums: List[int], m: dict) -> None:
			for i in range(len(nums)):
				for j in range(i + 1, len(nums)):
					prod = nums[i] * nums[j]
					sqrt = math.sqrt(prod)
					if sqrt in m:
						self.ans += m[sqrt]
		count(nums1, m2)
		count(nums2, m1)
		return self.ans


import collections

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		numsproddict = collections.defaultdict(int)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				numsproddict[nums1[i] * nums1[j]] += 1
		numsproddict2 = collections.defaultdict(int)
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				numsproddict2[nums2[i] * nums2[j]] += 1
		ans = 0
		for i in range(len(nums1)):
			ans += numsproddict2[nums1[i] * nums1[i]]
		for i in range(len(nums2)):
			ans += numsproddict[nums2[i] * nums2[i]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		squares1 = Counter()
		squares2 = Counter()
		for num in nums1:
			squares1[num * num] += 1
		for num in nums2:
			squares2[num * num] += 1
		numTriplets = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in squares2:
					numTriplets += squares2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in squares1:
					numTriplets += squares1[nums2[i] * nums2[j]]
		return numTriplets


from collections import defaultdict

class Solution:

	def getNumOfMatch(self, square, nums):
		res = 0
		h = defaultdict(int)
		n = len(nums)
		for v in nums:
			if square % v == 0:
				res += h[square // v]
				h[v] += 1
		return res

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for num in nums1:
			res += self.getNumOfMatch(num * num, nums2)
		for num in nums2:
			res += self.getNumOfMatch(num * num, nums1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = {}
		d2 = {}
		(cnt1, cnt2) = (0, 0)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] not in d1:
					d1[nums1[i] * nums1[j]] = 1
				else:
					d1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] not in d2:
					d2[nums2[i] * nums2[j]] = 1
				else:
					d2[nums2[i] * nums2[j]] += 1
		for i in range(len(nums1)):
			if nums1[i] ** 2 in d2:
				cnt1 += d2[nums1[i] ** 2]
		for i in range(len(nums2)):
			if nums2[i] ** 2 in d1:
				cnt2 += d1[nums2[i] ** 2]
		return cnt1 + cnt2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		result = 0
		sums = {}
		sums2 = {}
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in sums:
					sums[nums2[i] * nums2[j]] += 1
				else:
					sums[nums2[i] * nums2[j]] = 1
		for i in nums1:
			if i ** 2 in sums:
				result += sums[i ** 2]
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in sums2:
					sums2[nums1[i] * nums1[j]] += 1
				else:
					sums2[nums1[i] * nums1[j]] = 1
		for i in nums2:
			if i ** 2 in sums2:
				result += sums2[i ** 2]
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import Counter
		c1 = Counter()
		c2 = Counter()
		r1 = 0
		r2 = 0
		for i in range(len(nums1)):
			for j in range(len(nums1)):
				if i < j:
					c1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2)):
			for j in range(len(nums2)):
				if i < j:
					c2[nums2[i] * nums2[j]] += 1
		for i in nums2:
			r1 += c1[i * i]
		for i in nums1:
			r2 += c2[i * i]
		return r1 + r2


import collections

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		square1 = [e ** 2 for e in nums1]
		target1 = collections.Counter(square1)
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in target1:
					count += target1[nums2[i] * nums2[j]]
		square2 = [e ** 2 for e in nums2]
		target2 = collections.Counter(square2)
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in target2:
					count += target2[nums1[i] * nums1[j]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(rev, n1, n2) = (0, Counter(nums1), Counter(nums2))
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				t = (nums1[i] * nums1[j]) ** (1 / 2)
				if t == int(t) and t in n2:
					rev += n2[t]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				t = (nums2[i] * nums2[j]) ** (1 / 2)
				if t == int(t) and t in n1:
					rev += n1[t]
		return rev


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		hh = defaultdict(int)
		nums1.sort()
		for (m, i) in enumerate(nums1):
			hh[i * i] += 1
		h = defaultdict(int)
		for i in nums2:
			h[i] += 1
		r = 0
		print(h)
		for i in h:
			for j in h:
				if i <= j and i * j in hh:
					if i == j:
						r += h[i] * (h[i] - 1) // 2 * hh[i * j]
					else:
						r += h[i] * h[j] * hh[i * j]
		(nums1, nums2) = (nums2, nums1)
		hh = defaultdict(int)
		nums1.sort()
		for (m, i) in enumerate(nums1):
			hh[i * i] += 1
		h = defaultdict(int)
		for i in nums2:
			h[i] += 1
		print(h)
		for i in h:
			for j in h:
				if i <= j and i * j in hh:
					if i == j:
						r += h[i] * (h[i] - 1) // 2 * hh[i * j]
					else:
						r += h[i] * h[j] * hh[i * j]
		return r


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		(double1, double2) = (collections.Counter(), collections.Counter())
		for n in nums1:
			double1[n * n] += 1
		for n in nums2:
			double2[n * n] += 1
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in double2:
					res += double2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in double1:
					res += double1[nums2[i] * nums2[j]]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(dic1, dic2) = (collections.Counter(nums1), collections.Counter(nums2))
		ans = 0
		(m, n) = (len(nums1), len(nums2))
		for i in range(m):
			for j in range(i + 1, m):
				target = nums1[i] * nums1[j]
				sq = math.sqrt(target)
				if sq * sq == target:
					ans += dic2[sq]
		for i in range(n):
			for j in range(i + 1, n):
				target = nums2[i] * nums2[j]
				sq = math.sqrt(target)
				if sq * sq == target:
					ans += dic1[sq]
		return ans


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		mults = lambda arr, N: Counter([arr[i] * arr[j] for i in range(N) for j in range(N) if i != j])
		squares = lambda arr: list([x ** 2 for x in arr])
		count = 0
		(A, B) = (squares(nums1), mults(nums2, len(nums2)))
		(C, D) = (squares(nums2), mults(nums1, len(nums1)))
		for a in A:
			if a in B:
				count += B[a]
		for a in C:
			if a in D:
				count += D[a]
		return count // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(m1, m2) = (collections.Counter(), collections.Counter())
		result = 0
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				n = sqrt(nums1[i] * nums1[j])
				if n % 1 == 0:
					m1[n] += 1
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				n = sqrt(nums2[i] * nums2[j])
				if n % 1 == 0:
					m2[n] += 1
		for num in nums1:
			result += m2[num]
		for num in nums2:
			result += m1[num]
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		m = len(nums1)
		n = len(nums2)
		mat2 = [[0 for i in range(n)] for i in range(n)]

		def fillUpper(m, nums):
			mat = [[0 for i in range(m)] for i in range(m)]
			mapp1 = defaultdict(int)
			for i in range(m - 1):
				for j in range(i + 1, len(mat)):
					mapp1[nums[i] * nums[j]] += 1
			return mapp1
		mat1 = fillUpper(m, nums1)
		mat2 = fillUpper(n, nums2)
		res = 0
		for i in nums1:
			c = i ** 2
			if c in mat2:
				res += mat2[c]
		for i in nums2:
			c = i ** 2
			if c in mat1:
				res += mat1[c]
		return res


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(product_set1, product_set2) = (defaultdict(int), defaultdict(int))
		numss = [nums1, nums2]
		for n in range(2):
			if n == 0:
				s = product_set1
			else:
				s = product_set2
			nums = numss[n]
			for i in range(len(nums)):
				for j in range(i + 1, len(nums)):
					s[nums[i] * nums[j]] += 1
		ans = 0
		for n in range(2):
			if n == 0:
				s = product_set2
			else:
				s = product_set1
			nums = numss[n]
			for i in range(len(nums)):
				ans += s[nums[i] * nums[i]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		total = 0
		nums1Sum = {}
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				nums1Sum[nums1[i] * nums1[j]] = nums1Sum.get(nums1[i] * nums1[j], 0) + 1
		nums2Sum = {}
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				nums2Sum[nums2[i] * nums2[j]] = nums2Sum.get(nums2[i] * nums2[j], 0) + 1
		for num in nums1:
			if num * num in nums2Sum:
				total += nums2Sum[num * num]
		for num in nums2:
			if num * num in nums1Sum:
				total += nums1Sum[num * num]
		return total


class Solution:

	def numTripletsHelper(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_map = {}
		count = 0
		for i in nums1:
			if i in nums1_map:
				nums1_map[i] += 1
			else:
				nums1_map[i] = 1
		for i in nums2:
			i_2 = i * i
			seen = set({})
			for j in nums1:
				left = nums1_map[j]
				if i_2 / j == j:
					if (j, j) not in seen and left > 1:
						count += int(left * (left - 1) / 2)
						seen.add((j, j))
				elif i_2 / j in nums1_map and (int(i_2 / j), j) not in seen:
					right = nums1_map[i_2 / j]
					seen.add((int(i_2 / j), j))
					seen.add((j, int(i_2 / j)))
					count += left * right
		return count

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.numTripletsHelper(nums1, nums2) + self.numTripletsHelper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import defaultdict
		import math
		n = len(nums1)
		m = len(nums2)
		(dic1, dic2) = (defaultdict(int), defaultdict(int))
		for i in range(n):
			dic1[nums1[i]] += 1
		for i in range(m):
			dic2[nums2[i]] += 1
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				x = nums1[i] * nums1[j]
				y = math.sqrt(x)
				if y % 1 == 0:
					ans += dic2[y]
		for i in range(m):
			for j in range(i + 1, m):
				x = nums2[i] * nums2[j]
				y = math.sqrt(x)
				if y % 1 == 0:
					ans += dic1[y]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def check(l1, l2):
			res = {}
			j = 0
			while j < len(l2):
				k = j + 1
				while k < len(l2):
					res[l2[j] * l2[k]] = res.get(l2[j] * l2[k], 0) + 1
					k += 1
				j += 1
			ans = 0
			while l1:
				node = l1.pop()
				if node in res:
					ans += res[node]
			return ans
		squares1 = [x * x for x in nums1]
		squares2 = [x * x for x in nums2]
		return check(squares1, nums2) + check(squares2, nums1)


from collections import Counter
from typing import List

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		l1 = len(nums1)
		l2 = len(nums2)
		c1 = Counter()
		c2 = Counter()
		for j in range(l1):
			for k in range(j + 1, l1):
				c1[nums1[j] * nums1[k]] += 1
		for j in range(l2):
			for k in range(j + 1, l2):
				c2[nums2[j] * nums2[k]] += 1
		for i in range(l1):
			res += c2[nums1[i] * nums1[i]]
		for i in range(l2):
			res += c1[nums2[i] * nums2[i]]
		return res


class Solution:

	def numTriplets(self, num1: List[int], num2: List[int]) -> int:
		dic1 = {}
		for i in range(len(num1)):
			for j in range(i + 1, len(num1)):
				if num1[i] * num1[j] in dic1:
					dic1[num1[i] * num1[j]] += 1
				else:
					dic1[num1[i] * num1[j]] = 1
		dic2 = {}
		for i in range(len(num2)):
			for j in range(i + 1, len(num2)):
				if num2[i] * num2[j] in dic2:
					dic2[num2[i] * num2[j]] += 1
				else:
					dic2[num2[i] * num2[j]] = 1
		ans = 0
		for i in num1:
			if i * i in dic2:
				ans += dic2[i * i]
		for i in num2:
			if i * i in dic1:
				ans += dic1[i * i]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find(A, target):
			(l, r) = (0, len(A) - 1)
			ans = 0
			while l < r:
				s = A[l] * A[r]
				if s == target:
					i = l + 1
					while i < r and A[i] == A[l]:
						i += 1
					numL = i - l
					j = r - 1
					while j > l and A[j] == A[r]:
						j -= 1
					numR = r - j
					l = i
					r = j
					if i > j and A[i] == A[j]:
						ans += (r - l) * (r - l - 1) // 2
					else:
						ans += numL * numR
				elif s < target:
					l += 1
				else:
					r -= 1
			return ans
		ans = 0
		nums1.sort()
		nums2.sort()
		for n in nums1:
			ans += find(nums2, n * n)
		for n in nums2:
			ans += find(nums1, n * n)
		return ans


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def solve(aa, bb):
			res = 0
			cnt = defaultdict(int)
			for a in aa:
				for b in bb:
					b2 = b * b
					if b2 % a:
						continue
					res += cnt[b * b // a]
				cnt[a] += 1
			return res
		ans = solve(nums1, nums2) + solve(nums2, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import defaultdict
		if len(nums1) == 1 and len(nums2) == 1:
			return 0

		def twoproduct(nsquare, nums):
			countmap = defaultdict(int)
			total = 0
			for num in nums:
				if nsquare % num == 0:
					total += countmap.get(nsquare // num, 0)
					countmap[num] += 1
			return total
		ans = 0
		for num in nums1:
			ans += twoproduct(num ** 2, nums2)
		for num in nums2:
			ans += twoproduct(num ** 2, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def getProd(n1, n2):
			c2 = Counter(n2)
			res = 0
			for x in n1:
				prod = x ** 2
				for n in n2:
					if prod % n > 0:
						continue
					d = prod // n
					if d in c2:
						res += c2[d]
						if d == n:
							res -= 1
			return res
		r = 0
		r += getProd(nums1, nums2)
		r += getProd(nums2, nums1)
		return r // 2


import bisect

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(v2i1, v2i2) = (dict(), dict())
		(n1, n2) = (len(nums1), len(nums2))
		for i in range(0, n1):
			if not nums1[i] in v2i1:
				v2i1[nums1[i]] = []
			v2i1[nums1[i]].append(i)
		for i in range(0, n2):
			if not nums2[i] in v2i2:
				v2i2[nums2[i]] = []
			v2i2[nums2[i]].append(i)
		result = 0
		for z in nums1:
			z = z * z
			for x in v2i2:
				if z % x == 0 and z // x in v2i2:
					y = z // x
					if y != x:
						(js, ks) = (v2i2[x], v2i2[y])
						for j in js:
							k = bisect.bisect(ks, j)
							result += len(ks) - k
					else:
						result += len(v2i2[x]) * (len(v2i2[x]) - 1) // 2
		for z in nums2:
			z = z * z
			for x in v2i1:
				if z % x == 0 and z // x in v2i1:
					y = z // x
					if y != x:
						(js, ks) = (v2i1[x], v2i1[y])
						for j in js:
							k = bisect.bisect(ks, j)
							result += len(ks) - k
					else:
						result += len(v2i1[x]) * (len(v2i1[x]) - 1) // 2
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		cnt1_e = Counter()
		cnt1_ne = Counter()
		for i in range(len(nums1)):
			cnt1_e[nums1[i] ** 2] += 1
			for j in range(i + 1, len(nums1)):
				cnt1_ne[nums1[i] * nums1[j]] += 1
		cnt2_e = Counter()
		cnt2_ne = Counter()
		for i in range(len(nums2)):
			cnt2_e[nums2[i] ** 2] += 1
			for j in range(i + 1, len(nums2)):
				cnt2_ne[nums2[i] * nums2[j]] += 1
		res = 0
		for (k1, v1) in list(cnt1_e.items()):
			if k1 in list(cnt2_ne.keys()):
				res += v1 * cnt2_ne[k1]
		for (k2, v2) in list(cnt2_e.items()):
			if k2 in list(cnt1_ne.keys()):
				res += v2 * cnt1_ne[k2]
		return res


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for num in nums1:
			res += self.two_product(num ** 2, nums2)
		for num in nums2:
			res += self.two_product(num ** 2, nums1)
		return res

	def two_product(self, target, nums):
		(dic, res) = (defaultdict(int), 0)
		for (i, num) in enumerate(nums):
			if target % num:
				continue
			remain = target // num
			res += dic[remain]
			dic[num] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		t1 = dict(collections.Counter(nums1))
		t2 = dict(collections.Counter(nums2))
		c = 0
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				temp = math.sqrt(nums1[j] * nums1[k])
				if temp in t2:
					c += t2[temp]
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				temp = math.sqrt(nums2[j] * nums2[k])
				if temp in t1:
					c += t1[temp]
		return c


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		self.ans = 0

		def func(n1, n2):
			for prod in n1:
				(i, j) = (0, len(n2) - 1)
				while i < j:
					if n2[i] == n2[j]:
						if n2[i] * n2[j] != prod * prod:
							break
						n = j - i + 1
						self.ans += n * (n - 1) // 2
						break
					if n2[i] * n2[j] == prod * prod:
						temp = n2[i]
						(t1, t2) = (0, 0)
						while i < j and n2[i] == temp:
							t1 += 1
							i += 1
						temp = n2[j]
						while i <= j and n2[j] == temp:
							t2 += 1
							j -= 1
						self.ans += t1 * t2
					elif n2[i] * n2[j] > prod * prod:
						j -= 1
					else:
						i += 1
		nums1.sort()
		nums2.sort()
		func(nums1, nums2)
		func(nums2, nums1)
		return self.ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(arr, match):
			n = len(arr)
			cnt = 0
			for i in range(n):
				for j in range(i + 1, n):
					val = math.sqrt(arr[i] * arr[j])
					if match.get(val):
						cnt += match[val]
			return cnt
		(freq1, freq2) = (collections.Counter(nums1), collections.Counter(nums2))
		return count(nums1, freq2) + count(nums2, freq1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import Counter
		C1 = Counter()
		C2 = Counter()
		for num in nums1:
			C1[num * num] += 1
		for num in nums2:
			C2[num * num] += 1
		res = 0
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				res += C2[nums1[i] * nums1[j]]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				res += C1[nums2[i] * nums2[j]]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1: List[int], nums2: List[int]) -> int:
			res = 0
			counter = Counter(nums2)
			for n1 in nums1:
				sq = n1 * n1
				for n2 in nums2:
					if sq % n2 == 0:
						num = sq / n2
						res += counter[num]
						if n1 == n2:
							res -= 1
			return res
		return int((helper(nums1, nums2) + helper(nums2, nums1)) / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		result = 0
		dict1 = dict()
		dict2 = dict()
		for x in nums1:
			if x in dict1:
				dict1[x] += 1
			else:
				dict1[x] = 1
		for x in nums2:
			if x in dict2:
				dict2[x] += 1
			else:
				dict2[x] = 1
		for x in nums1:
			squar = x ** 2
			for y in nums2:
				if squar / y in dict2:
					if squar / y == y:
						result += dict2[squar / y] - 1
					else:
						result += dict2[squar / y]
		for x in nums2:
			squar = x ** 2
			for y in nums1:
				if squar / y in dict1:
					if squar / y == y:
						result += dict1[squar / y] - 1
					else:
						result += dict1[squar / y]
		return int(result / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		d1 = collections.defaultdict(list)
		for (i, num) in enumerate(nums1):
			d1[num].append(i)
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				sqrt = (nums2[i] * nums2[j]) ** 0.5
				if sqrt == int(sqrt) and sqrt in d1:
					res += len(d1[sqrt])
		d2 = collections.defaultdict(list)
		for (i, num) in enumerate(nums2):
			d2[num].append(i)
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				sqrt = (nums1[i] * nums1[j]) ** 0.5
				if sqrt == int(sqrt) and sqrt in d2:
					res += len(d2[sqrt])
		return res


class Solution:

	def fact(self, n):
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res

	def getCombo(self, n):
		return int(self.fact(n) / (self.fact(2) * self.fact(n - 2)))

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = {}
		for n in nums1:
			if n not in d1:
				d1[n] = 1
			else:
				d1[n] += 1
		d2 = {}
		for n in nums2:
			if n not in d2:
				d2[n] = 1
			else:
				d2[n] += 1
		tot = 0
		sq1 = 0
		for n in nums1:
			s = n * n
			for d in d2:
				if s % d == 0:
					div = s // d
					if div in d2:
						if div == d:
							sq1 += self.getCombo(d2[div])
						else:
							tot += d2[div] * d2[d]
		tot1 = tot // 2
		tot = 0
		sq2 = 0
		for n in nums2:
			s = n * n
			for d in d1:
				if s % d == 0:
					div = s // d
					if div in d1:
						if div == d:
							sq2 += self.getCombo(d1[div])
						else:
							tot += d1[div] * d1[d]
		tot2 = tot // 2
		return tot1 + tot2 + sq1 + sq2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def f(n):
			if n == 2 or n == 1:
				return 1
			return f(n - 1) + n - 1

		def yanzheng(a, num):
			a = a * a
			head = 0
			end = len(num) - 1
			count = 0
			while True:
				headlen = 1
				endlen = 1
				if head >= end:
					return count
				if num[head] * num[end] > a:
					end -= 1
				elif num[head] * num[end] < a:
					head += 1
				elif num[head] * num[end] == a:
					if num[head] == num[end]:
						count += f(end - head + 1)
						head = end
					elif num[head] == num[head + 1] or num[end] == num[end - 1]:
						while num[head] == num[head + headlen]:
							headlen += 1
						while num[end] == num[end - endlen]:
							endlen += 1
						count += headlen * endlen
						head += headlen
						end -= endlen
					else:
						count += 1
						end -= 1
		count = 0
		for i in nums1:
			count += yanzheng(i, nums2)
		for i in nums2:
			count += yanzheng(i, nums1)
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		n1 = defaultdict(int)
		for n in nums1:
			n1[n] += 1
		n2 = defaultdict(int)
		for n in nums2:
			n2[n] += 1
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				prod = nums1[j] * nums1[k]
				ans += n2[prod ** 0.5]
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				prod = nums2[j] * nums2[k]
				ans += n1[prod ** 0.5]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n = len(nums1)
		m = len(nums2)
		nums1prod = [[nums1[i] * nums1[j] for i in range(n)] for j in range(n)]
		nums2prod = [[nums2[i] * nums2[j] for i in range(m)] for j in range(m)]
		nums1sq = [x ** 2 for x in nums1]
		nums2sq = [x ** 2 for x in nums2]
		hm1sq = Counter(nums1sq)
		hm2sq = Counter(nums2sq)
		trip = 0
		for i in range(n):
			for j in range(i + 1, n):
				if nums1prod[i][j] in hm2sq:
					trip += hm2sq[nums1prod[i][j]]
		for i in range(m):
			for j in range(i + 1, m):
				if nums2prod[i][j] in hm1sq:
					trip += hm1sq[nums2prod[i][j]]
		return trip


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def getProd(nums):
			dict1 = {}
			for i in range(len(nums)):
				for j in range(len(nums)):
					if i != j:
						prod = nums[i] * nums[j]
						if prod not in dict1:
							dict1[prod] = 0
						dict1[prod] += 1
			return dict1
		res = 0
		d1 = getProd(nums1)
		for x in nums2:
			if x ** 2 in d1:
				res += d1[x ** 2]
		d2 = getProd(nums2)
		for x in nums1:
			if x ** 2 in d2:
				res += d2[x ** 2]
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(n1, n2):
			l2 = len(n2)
			cnt = Counter()
			for k in range(l2):
				for j in range(k):
					v = n2[k] * n2[j]
					cnt[v] += 1
			ans = 0
			for x in n1:
				ans += cnt[x * x]
			return ans
		return count(nums1, nums2) + count(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		jk_1 = {}
		for i in range(len(nums1)):
			for j in range(len(nums1)):
				if i != j:
					t = nums1[i] * nums1[j]
					if t in jk_1:
						jk_1[t] += 1
					else:
						jk_1[t] = 1
		jk_2 = {}
		for i in range(len(nums2)):
			for j in range(len(nums2)):
				if i != j:
					t = nums2[i] * nums2[j]
					if t in jk_2:
						jk_2[t] += 1
					else:
						jk_2[t] = 1
		c = 0
		for x in nums1:
			if x * x in jk_2:
				c += jk_2[x * x]
		for x in nums2:
			if x * x in jk_1:
				c += jk_1[x * x]
		return c // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		triplets = 0
		for (lst1, lst2) in ((nums1, nums2), (nums2, nums1)):
			for square in (n ** 2 for n in lst1):
				seen = defaultdict(int)
				for n in lst2:
					if square % n == 0:
						triplets += seen[square // n]
					seen[n] += 1
		return triplets


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(c1, c2) = (collections.Counter(nums1), collections.Counter(nums2))
		res = 0
		for n1 in nums1:
			x = n1 ** 2
			for n2 in nums2:
				if x % n2 == 0 and x // n2 in c2:
					if x // n2 == n2:
						res += c2[x // n2] - 1
					else:
						res += c2[x // n2]
		for n2 in nums2:
			x = n2 ** 2
			for n1 in nums1:
				if x % n1 == 0 and x // n1 in c1:
					if x // n1 == n1:
						res += c1[x // n1] - 1
					else:
						res += c1[x // n1]
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def two(target, nums):
			counter = collections.defaultdict(int)
			res = 0
			for num in nums:
				if target % num == 0:
					res += counter[target // num]
				counter[num] += 1
			return res
		res = 0
		for num in nums1:
			res += two(num * num, nums2)
		for num in nums2:
			res += two(num * num, nums1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = collections.Counter(nums1)
		count2 = collections.Counter(nums2)
		result = 0
		for num1 in count1:
			for num2 in count2:
				if num1 ** 2 % num2 == 0 and num1 ** 2 // num2 in count2:
					target = num1 ** 2 // num2
					if target == num2:
						if count2[num2] > 1:
							result += count1[num1] * (count2[num2] * (count2[num2] - 1) // 2)
					else:
						result += count1[num1] * (count2[num2] * count2[target] / 2)
		for num2 in count2:
			for num1 in count1:
				if num2 ** 2 % num1 == 0 and num2 ** 2 // num1 in count1:
					target = num2 ** 2 // num1
					if target == num1:
						if count1[num1] > 1:
							result += count2[num2] * (count1[num1] * (count1[num1] - 1) // 2)
					else:
						result += count2[num2] * (count1[num1] * count1[target] / 2)
		return int(result)


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_sq = [num ** 2 for num in nums1]
		nums2_sq = [num ** 2 for num in nums2]
		cache = defaultdict(int)
		count = 0
		for index in range(len(nums2)):
			number = nums2[index]
			if cache[number]:
				count += cache[number]
			for sub_index in range(len(nums1_sq)):
				square = nums1_sq[sub_index]
				(q, r) = divmod(square, number)
				if not r:
					cache[q] += 1
		cache = defaultdict(int)
		for index in range(len(nums1)):
			number = nums1[index]
			if cache[number]:
				count += cache[number]
			for sub_index in range(len(nums2_sq)):
				square = nums2_sq[sub_index]
				(q, r) = divmod(square, number)
				if not r:
					cache[q] += 1
		return count


class Solution:

	def find(self, n1, n2, c1):
		res = 0
		for j in range(len(n2)):
			for k in range(j + 1, len(n2)):
				t = n2[j] * n2[k]
				sqrt = t ** 0.5
				if sqrt ** 2 != t:
					continue
				try:
					i = c1[sqrt]
				except KeyError:
					i = 0
				res += i
		return res

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		n1 = set(nums1)
		n2 = set(nums2)
		c1 = {}
		c2 = {}
		for x in nums1:
			try:
				c1[x] += 1
			except KeyError:
				c1[x] = 1
		for x in nums2:
			try:
				c2[x] += 1
			except KeyError:
				c2[x] = 1
		res += self.find(nums1, nums2, c1)
		res += self.find(nums2, nums1, c2)
		return res


from collections import Counter
from itertools import combinations

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			cnt = Counter()
			for (a, b) in combinations(nums1, 2):
				cnt[a * b] += 1
			return sum((cnt[x * x] for x in nums2))
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def calculate(self, nums1, nums2):
		a = [0] * 100001
		for i in nums1:
			a[i] += 1
		ans = 0
		for num in nums2:
			for i in nums1:
				if num * num % i == 0 and num * num // i <= 100000:
					ans += a[num * num // i]
					if num == i:
						ans -= 1
		ans = ans // 2
		return ans

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.calculate(nums1, nums2) + self.calculate(nums2, nums1)


from collections import defaultdict

class Solution:

	def numTriplets(self, num1: List[int], num2: List[int]) -> int:
		d11 = defaultdict(list)
		d12 = defaultdict(list)
		for i in range(len(num1)):
			for j in range(i, len(num1)):
				if i == j:
					d11[num1[i] ** 2].append(i)
				else:
					d12[num1[i] * num1[j]].append((i, j))
		d21 = defaultdict(list)
		d22 = defaultdict(list)
		for i in range(len(num2)):
			for j in range(i, len(num2)):
				if i == j:
					d21[num2[i] ** 2].append(i)
				else:
					d22[num2[i] * num2[j]].append((i, j))
		ans = 0
		for key in d11:
			if key in d22:
				ans += len(d11[key]) * len(d22[key])
		for key in d21:
			if key in d12:
				ans += len(d21[key]) * len(d12[key])
		return ans


class Solution:

	def numTriplets(self, a1: List[int], a2: List[int]) -> int:
		d = {}
		n1 = len(a1)
		n2 = len(a2)
		for i in range(n1):
			for j in range(i + 1, n1):
				if a1[i] * a1[j] in list(d.keys()):
					d[a1[i] * a1[j]] += 1
				else:
					d[a1[i] * a1[j]] = 1
		c = 0
		for x in a2:
			if x * x in list(d.keys()):
				c += d[x * x]
		e = {}
		for i in range(n2):
			for j in range(i + 1, n2):
				if a2[i] * a2[j] in list(e.keys()):
					e[a2[i] * a2[j]] += 1
				else:
					e[a2[i] * a2[j]] = 1
		for x in a1:
			if x * x in list(e.keys()):
				c += e[x * x]
		return c


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		count = 0
		nums1m = [x * x for x in nums1]
		nums2m = [x * x for x in nums2]
		d1 = defaultdict(int)
		d2 = defaultdict(int)
		for num in nums1:
			d1[num] += 1
		for num in nums2:
			d2[num] += 1
		for num in nums1m:
			for j in range(len(nums2)):
				if nums2[j] > num:
					break
				if num % nums2[j] != 0:
					continue
				left = num // nums2[j]
				if left in d2:
					if left == nums2[j]:
						count += d2[left] - 1
					else:
						count += d2[left]
		for num in nums2m:
			for j in range(len(nums1)):
				if nums1[j] > num:
					break
				if num % nums1[j] != 0:
					continue
				left = num // nums1[j]
				if left in d1:
					if left == nums1[j]:
						count += d1[left] - 1
					else:
						count += d1[left]
		return count // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def one_type(nums1, nums2):
			(res, counter) = (0, collections.Counter(nums2))
			for num1 in nums1:
				prod = num1 * num1
				for num2 in nums2:
					target = prod / num2
					if target in counter:
						res += counter[target] - (target == num1)
			return res // 2
		return one_type(nums1, nums2) + one_type(nums2, nums1)


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		c1 = Counter(nums1)
		c2 = Counter(nums2)
		for i in nums1:
			for j in nums2:
				j2 = j * j
				ji = j2 // i
				if ji * i == j2:
					res += c1[j2 // i]
					if ji == i:
						res -= 1
				i2 = i * i
				ij = i2 // j
				if ij * j == i2:
					res += c2[i2 // j]
					if ij == j:
						res -= 1
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(d1, d2) = ({}, {})
		for i in range(len(nums1)):
			for j in range(i):
				d1[nums1[i] * nums1[j]] = d1.get(nums1[i] * nums1[j], 0) + 1
		for i in range(len(nums2)):
			for j in range(i):
				d2[nums2[i] * nums2[j]] = d2.get(nums2[i] * nums2[j], 0) + 1
		return sum((d1.get(i * i, 0) for i in nums2)) + sum((d2.get(j * j, 0) for j in nums1))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(target, nums):
			dic = collections.defaultdict(int)
			count = 0
			for num in nums:
				if target % num == 0 and target // num in dic:
					count += dic[target // num]
				dic[num] += 1
			return count
		ans = 0
		for x in nums1:
			ans += helper(x ** 2, nums2)
		for x in nums2:
			ans += helper(x ** 2, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(n, nums):
			(cnt, d) = (0, collections.defaultdict(int))
			for i in nums:
				if n % i == 0 and n // i in d:
					cnt += d[n // i]
				d[i] += 1
			return cnt
		res = 0
		for i in nums1:
			res += count(i * i, nums2)
		for i in nums2:
			res += count(i * i, nums1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		fin = 0
		for i in range(len(nums1)):
			res = 0
			fin += self.finder(nums1[i], nums2, res)
		for i in range(len(nums2)):
			res = 0
			fin += self.finder(nums2[i], nums1, res)
		return fin

	def finder(self, square, arr, res):
		res = 0
		n = square * square
		di = {}
		for i in range(len(arr)):
			if n % arr[i] == 0:
				p = n // arr[i]
				if arr[i] in di:
					res += di[arr[i]]
				if p in di:
					di[p] += 1
				else:
					di[p] = 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProduct(arr, target):
			d = {}
			ret = 0
			for x in arr:
				if target % x == 0 and target // x in d:
					ret += d[target // x]
				if x in d:
					d[x] += 1
				else:
					d[x] = 1
			return ret
		ret = 0
		for x in nums1:
			sq = x ** 2
			ret += twoProduct(nums2, sq)
		for x in nums2:
			sq = x ** 2
			ret += twoProduct(nums1, sq)
		return ret


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def countTriplets(nums1, nums2):
			count = 0
			for (index, val) in enumerate(nums1):
				target = int(val ** 2)
				lookup = defaultdict(int)
				for (index2, val2) in enumerate(nums2):
					if target / val2 in lookup:
						count += lookup[target // val2]
					lookup[val2] += 1
			return count
		count1 = countTriplets(nums1, nums2)
		count2 = countTriplets(nums2, nums1)
		return count1 + count2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find(nums1, nums2):
			res = 0
			for x in nums1:
				cnt = defaultdict(int)
				for y in nums2:
					if x * x % y == 0:
						res += cnt[x * x // y]
					cnt[y] += 1
			return res
		ret = 0
		ret += find(nums1, nums2)
		ret += find(nums2, nums1)
		return ret


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = collections.Counter(nums1)
		c2 = collections.Counter(nums2)
		r = 0
		for n in nums1:
			for a in nums2:
				t = n * n // a
				if t * a == n * n:
					if t == a:
						r = r + (c2[t] - 1) / 2
					else:
						r = r + c2[t] / 2
		for a in nums1:
			for n in nums2:
				t = n * n // a
				if t * a == n * n:
					if t == a:
						r = r + (c1[t] - 1) / 2
					else:
						r = r + c1[t] / 2
		return math.floor(r)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProduct(target, nums):
			cnt = 0
			currMap = collections.defaultdict(lambda : 0)
			for num in nums:
				if target % num == 0 and target // num in currMap:
					cnt += currMap[target // num]
				currMap[num] += 1
			return cnt
		res = 0
		for num1 in nums1:
			target = num1 * num1
			res += twoProduct(target, nums2)
		for num2 in nums2:
			target = num2 * num2
			res += twoProduct(target, nums1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = {}
		d2 = {}
		for i in nums1:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		for i in nums2:
			if i in d2:
				d2[i] += 1
			else:
				d2[i] = 1
		count = 0
		for key in d1:
			for x in d2:
				if key ** 2 % x == 0:
					if key ** 2 // x == x:
						if d2[x] > 1:
							count += d1[key] * (d2[x] - 1) * d2[x]
					elif key ** 2 // x in d2:
						count += d1[key] * d2[x] * d2[key ** 2 // x]
		for key in d2:
			for x in d1:
				if key ** 2 % x == 0:
					if key ** 2 // x == x:
						if d1[x] > 1:
							count += d2[key] * (d1[x] - 1) * d1[x]
					elif key ** 2 // x in d1:
						count += d2[key] * d1[x] * d1[key ** 2 // x]
		return count // 2


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.triples(nums1, nums2) + self.triples(nums2, nums1)

	def triples(self, nums1, nums2):
		res = 0
		for n1 in nums1:
			visited = defaultdict(int)
			for n2 in nums2:
				if n1 * n1 % n2 == 0:
					res += visited[n1 * n1 // n2]
				visited[n2] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProd(B, sq):
			d = defaultdict(int)
			cnt = 0
			for val in B:
				if sq % val == 0:
					cnt += d.get(sq // val, 0)
				d[val] += 1
			return cnt

		def poss(A, B):
			ret = 0
			(m, n) = (len(A), len(B))
			for x in A:
				ret += twoProd(B, x * x)
			return ret
		return poss(nums1, nums2) + poss(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(comp1, comp2) = (defaultdict(set), defaultdict(set))
		if not nums1 or not nums2:
			return 0
		(n, m) = (len(nums1), len(nums2))
		ans = 0
		(c1, c2) = (Counter([num ** 2 for num in nums1]), Counter([num ** 2 for num in nums2]))
		for i in range(n):
			for j in range(i + 1, n):
				prod = nums1[i] * nums1[j]
				ans += c2[prod]
		for i in range(m):
			for j in range(i + 1, m):
				prod = nums2[i] * nums2[j]
				ans += c1[prod]
		return ans


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		self.res = 0

		def count(a1, a2):
			for e1 in [e * e for e in a1]:
				m = defaultdict(int)
				for e2 in a2:
					if e1 % e2 == 0:
						self.res += m[e1 // e2]
					m[e2] += 1
		count(nums1, nums2)
		count(nums2, nums1)
		return self.res


from itertools import combinations
from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		num1Sq = [i * i for i in nums1]
		num2Sq = [i * i for i in nums2]
		c1 = Counter(num1Sq)
		c2 = Counter(num2Sq)
		comb1 = list(combinations(nums1, 2))
		comb2 = list(combinations(nums2, 2))
		res = 0
		for i in comb1:
			res += c2[i[0] * i[1]]
		for i in comb2:
			res += c1[i[0] * i[1]]
		return res


def pairs(arr):
	for i in range(0, len(arr) - 1):
		for j in range(i + 1, len(arr)):
			yield (arr[i], arr[j])

def count(A, B):
	tally_A = {}
	for elem in A:
		tally_A.setdefault(elem ** 2, 0)
		tally_A[elem ** 2] += 1
	tally_B = {}
	for (e, f) in pairs(B):
		tally_B.setdefault(e * f, 0)
		tally_B[e * f] += 1
	return sum((tally_A[e] * tally_B[e] for e in tally_A if e in tally_B))

class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:
		return count(A, B) + count(B, A)


from collections import Counter
from itertools import combinations

class Solution:

	def numTriplets(self, nums1, nums2) -> int:
		c_nums1 = Counter(nums1)
		c_nums2 = Counter(nums2)
		res = 0
		self_product1 = Counter()
		cross_product1 = Counter()
		self_product2 = Counter()
		cross_product2 = Counter()
		for (k, v) in c_nums1.items():
			self_product1[k ** 2] += v * (v - 1) // 2
		for (k, v) in c_nums2.items():
			self_product2[k ** 2] += v * (v - 1) // 2
		for comb in combinations(c_nums1.keys(), 2):
			(p, v) = comb
			cross_product1[p * v] += c_nums1[p] * c_nums1[v]
		for comb in combinations(c_nums2.keys(), 2):
			(p, v) = comb
			cross_product2[p * v] += c_nums2[p] * c_nums2[v]
		for (k, v) in c_nums1.items():
			target = k ** 2
			if target in cross_product2:
				res += v * cross_product2[target]
			if target in self_product2:
				res += v * self_product2[target]
		for (k, v) in c_nums2.items():
			target = k ** 2
			if target in cross_product1:
				res += v * cross_product1[target]
			if target in self_product1:
				res += v * self_product1[target]
		return res


from collections import Counter

class Solution:

	def mul(self, x):
		ans = []
		n = len(x)
		for i in range(n - 1):
			for j in range(i + 1, n):
				ans.append(x[i] * x[j])
		return ans

	def count(self, x, y):
		ans = 0
		cx = Counter(x)
		cy = Counter(y)
		same = set(x).intersection(set(y))
		for num in same:
			ans += cx[num] * cy[num]
		return ans

	def numTriplets(self, a: List[int], b: List[int]) -> int:
		ans = 0
		asq = [i * i for i in a]
		bsq = [i * i for i in b]
		aa = self.mul(a)
		bb = self.mul(b)
		ans += self.count(asq, bb)
		ans += self.count(bsq, aa)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(n1, n2):
			ret = 0
			for x in n1:
				seen = collections.defaultdict(int)
				for y in n2:
					if x * x % y == 0:
						ret += seen[x * x // y]
					seen[y] += 1
			return ret
		return count(nums1, nums2) + count(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cal(arr1, arr2):
			tmp = 0
			for n1 in arr1:
				n1pow2 = n1 * n1
				h = collections.defaultdict(int)
				for (idx, n2) in enumerate(arr2):
					if n1pow2 / n2 in h:
						tmp += h[n1pow2 // n2]
					h[n2] += 1
			return tmp
		return cal(nums1, nums2) + cal(nums2, nums1)


from math import sqrt

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		numTwoHave = defaultdict(lambda : 0)
		numOneHave = defaultdict(lambda : 0)
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				numTwoHave[sqrt(nums2[j] * nums2[k])] += 1
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				numOneHave[sqrt(nums1[j] * nums1[k])] += 1
		triplets = 0
		for num in nums1:
			if num in numTwoHave:
				triplets += numTwoHave[num]
		for num in nums2:
			if num in numOneHave:
				triplets += numOneHave[num]
		return triplets


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for num in nums1:
			res += self.two_product(num ** 2, nums2)
		for num in nums2:
			res += self.two_product(num ** 2, nums1)
		return res

	def two_product(self, target, nums):
		(dic, res) = ({}, 0)
		for (i, num) in enumerate(nums):
			if target % num:
				continue
			remain = target // num
			res += dic.get(remain, 0)
			dic[num] = dic.get(num, 0) + 1
		return res


import itertools

def calCross(nums):
	res = []
	pairs = list(itertools.combinations(nums, 2))
	for (i, j) in pairs:
		res.append(i * j)
	return res

def commonCnt(nums1, nums2):
	res = 0
	cross = set(nums1) & set(nums2)
	for e in cross:
		res += nums1.count(e) * nums2.count(e)
	return res

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		square1 = [e * e for e in nums1]
		square2 = [e * e for e in nums2]
		cross1 = calCross(nums1)
		cross2 = calCross(nums2)
		res = commonCnt(square1, cross2)
		res += commonCnt(square2, cross1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(l1, l2):
			d = {}
			for c in l1:
				if c ** 2 in d:
					d[c ** 2] += 1
				else:
					d[c ** 2] = 1
			r = {}
			for c in l2:
				if c in r:
					r[c] += 1
				else:
					r[c] = 1
			count = 0
			for c in l2:
				for s in d:
					(res, c2) = (s % c, s // c)
					if res == 0 and c2 in r:
						if c2 != c:
							count += r[c2] * d[s]
						else:
							count += (r[c2] - 1) * d[s]
			return count // 2
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0

		def cal(n, nums):
			nonlocal ans
			d = defaultdict(int)
			for num in nums:
				if n % num == 0:
					ans += d[n / num]
				d[num] += 1
		for n in nums1:
			cal(n * n, nums2)
		for n in nums2:
			cal(n * n, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		set1 = set(nums1)
		set2 = set(nums2)
		lookup1 = defaultdict(int)

		def ncr(n, r):
			from math import factorial
			return factorial(n) // factorial(r) // factorial(n - r)

		def countTriplets(nums1, nums2):
			lookup = defaultdict(int)
			count = 0
			for (index, val) in enumerate(nums1):
				target = val ** 2
				lookup = defaultdict(int)
				for (index2, val2) in enumerate(nums2):
					if target % val2 == 0:
						if target // val2 in lookup:
							count += lookup[target // val2]
					lookup[val2] += 1
			return count
		count1 = countTriplets(nums1, nums2)
		count2 = countTriplets(nums2, nums1)
		return count1 + count2


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for num in nums1:
			res += self.twoProduct(num * num, nums2)
		for num in nums2:
			res += self.twoProduct(num * num, nums1)
		return res

	def twoProduct(self, val, nums):
		(prod, res) = (defaultdict(int), 0)
		for num in nums:
			res += prod[num]
			(q, r) = divmod(val, num)
			if r == 0:
				prod[q] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.num(nums1, nums2) + self.num(nums2, nums1)

	def num(self, nums1, nums2):
		possibleSquares = {}
		possibleProducts = {}
		for (idx, x) in enumerate(nums1):
			square = x * x
			if square in possibleSquares:
				possibleSquares[square].append(idx)
			else:
				possibleSquares[square] = [idx]
		for x in range(len(nums2) - 1):
			for y in range(x + 1, len(nums2)):
				product = nums2[x] * nums2[y]
				if product in possibleProducts:
					possibleProducts[product].append((x, y))
				else:
					possibleProducts[product] = [(x, y)]
		result = 0
		for s in possibleSquares:
			if s in possibleProducts:
				result += len(possibleSquares[s]) * len(possibleProducts[s])
		return result


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:
		res = 0

		def count(n2, arr):
			res = 0
			c = defaultdict(int)
			for n in arr:
				if n2 % n == 0:
					res += c[n2 // n]
				c[n] += 1
			return res
		for (i, n) in enumerate(A):
			res += count(n * n, B)
		for (i, n) in enumerate(B):
			res += count(n * n, A)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		count = self.counttrip(nums1, nums2)
		count += self.counttrip(nums2, nums1)
		return int(count)

	def counttrip(self, nums1, nums2):
		count = 0
		for i in nums1:
			target = i * i
			dictn = defaultdict(int)
			for (j, x) in enumerate(nums2):
				rem = target / x
				if rem in dictn:
					count += dictn[rem]
				dictn[x] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for n1 in nums1:
			n1 = n1 ** 2
			visited = collections.defaultdict(int)
			for n2 in nums2:
				if n1 % n2 == 0 and visited[n1 // n2] > 0:
					res += visited[n1 // n2]
				visited[n2] += 1
		for n2 in nums2:
			n2 = n2 ** 2
			visited = collections.defaultdict(int)
			for n1 in nums1:
				if n2 % n1 == 0 and visited[n2 // n1] > 0:
					res += visited[n2 // n1]
				visited[n1] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			s1 = Counter(nums1)
			s2 = Counter(nums2)
			cnt = 0
			for i in range(len(nums1)):
				need = nums1[i] * nums1[i]
				if need == 0:
					if 0 in s2:
						cnt += s2[0] * (len(num2) - 1) - (s2[0] - 1) * (s2[0] - 1)
					else:
						cnt += 0
				else:
					for j in range(len(nums2)):
						kk = need / nums2[j]
						if kk in s2:
							if nums2[j] != kk:
								cnt += s2[kk] / 2
							else:
								cnt += (s2[kk] - 1) / 2
			return int(cnt)
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			ret = 0
			C = collections.Counter(nums2)
			s = sorted(C)
			for n in nums1:
				ret += C[n] * (C[n] - 1) // 2
				nn = n * n
				for d in s:
					if d >= n:
						break
					if nn % d == 0:
						ret += C[d] * C[nn // d]
			return ret
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def tow_product(A, target):
			d = {}
			res = 0
			for x in A:
				if target % x == 0 and target // x in d:
					res += d[target // x]
				d[x] = d.get(x, 0) + 1
			return res

		def count(nums1, nums2):
			res = 0
			last_cnt = 0
			for i in range(len(nums1)):
				if i > 0 and nums1[i] == nums1[i - 1]:
					res += last_cnt
				else:
					last_cnt = tow_product(nums2, nums1[i] ** 2)
					res += last_cnt
			return res
		nums1 = sorted(nums1)
		nums2 = sorted(nums2)
		return count(nums1, nums2) + count(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n = len(nums1)
		m = len(nums2)
		res = 0
		for x in nums1:
			t = x * x
			m = {}
			for y in nums2:
				if t % y == 0:
					res += m.get(t // y, 0)
				m[y] = m.get(y, 0) + 1
		for y in nums2:
			t = y * y
			m = {}
			for x in nums1:
				if t % x == 0:
					res += m.get(t // x, 0)
				m[x] = m.get(x, 0) + 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		set1 = set(nums1)
		set2 = set(nums2)
		lookup1 = defaultdict(int)

		def countTriplets(nums1, nums2):
			lookup = defaultdict(int)
			count = 0
			for (index, val) in enumerate(nums1):
				target = val ** 2
				lookup = defaultdict(int)
				for (index2, val2) in enumerate(nums2):
					if target % val2 == 0:
						if target // val2 in lookup:
							count += lookup[target // val2]
					lookup[val2] += 1
			return count
		count1 = countTriplets(nums1, nums2)
		count2 = countTriplets(nums2, nums1)
		return count1 + count2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		muti_set1 = set()
		muti_set2 = set()
		muti_dict1 = dict()
		muti_dict2 = dict()
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				v = nums1[i] * nums1[j]
				if v in muti_set1:
					muti_dict1[str(v)] = muti_dict1[str(v)] + 1
				else:
					muti_dict1[str(v)] = 1
					muti_set1.add(v)
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				v = nums2[i] * nums2[j]
				if v in muti_set2:
					muti_dict2[str(v)] = muti_dict2[str(v)] + 1
				else:
					muti_dict2[str(v)] = 1
					muti_set2.add(v)
		res = 0
		print(muti_set1)
		print(muti_set2)
		for _ in nums1:
			if _ * _ in muti_set2:
				res = res + muti_dict2[str(_ * _)]
		for _ in nums2:
			if _ * _ in muti_set1:
				res = res + muti_dict1[str(_ * _)]
		return res


from collections import defaultdict as dt

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		cnt = 0
		for x in nums1:
			d = dt(int)
			for y in nums2:
				if x * x % y == 0 and x * x // y in d:
					cnt += d[x * x // y]
				d[y] += 1
		for x in nums2:
			d = dt(int)
			for y in nums1:
				if x * x % y == 0 and x * x // y in d:
					cnt += d[x * x // y]
				d[y] += 1
		return cnt


from collections import defaultdict

def two_product(array, target):
	counter = defaultdict(int)
	count = 0
	for (index, value) in enumerate(array):
		candidate = target / value
		if candidate in counter:
			count += counter[candidate]
		counter[value] += 1
	return count

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		for num in nums1:
			count += two_product(nums2, num * num)
		for num in nums2:
			count += two_product(nums1, num * num)
		return count


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			ans = 0
			for num1 in nums1:
				exist = defaultdict(int)
				v = num1 * num1
				for num2 in nums2:
					if v % num2 == 0 and v / num2 in exist:
						ans += exist[v / num2]
					exist[num2] += 1
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		import collections
		h1 = {}
		s1 = collections.Counter()
		h2 = {}
		s2 = collections.Counter()
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				s1[nums1[i] * nums1[j]] += 1
				h1[i, j] = nums1[i] * nums1[j]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				s2[nums2[i] * nums2[j]] += 1
				h2[i, j] = nums2[i] * nums2[j]
		ans = 0
		for i in range(len(nums1)):
			if nums1[i] * nums1[i] in s2:
				ans += s2[nums1[i] * nums1[i]]
		for i in range(len(nums2)):
			if nums2[i] * nums2[i] in s1:
				ans += s1[nums2[i] * nums2[i]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cntProduct(square: int, nums: List[int]) -> int:
			(num_count, cnt) = ({}, 0)
			for num in nums:
				if square % num == 0:
					cnt += num_count.get(square // num, 0)
				num_count[num] = 1 + num_count.get(num, 0)
			return cnt
		return sum((cntProduct(num ** 2, nums2) for num in nums1)) + sum((cntProduct(num ** 2, nums1) for num in nums2))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def cnt(tot, arr):
			mp = {}
			ans = 0
			for val in arr:
				if tot % val == 0 and tot / val in mp:
					ans += mp[tot / val]
				mp[val] = mp.get(val, 0) + 1
			return ans

		def helper(arr1, arr2):
			last_num = None
			last_ans = None
			ans = 0
			for num in arr1:
				if num == last_num:
					ans += last_ans
				else:
					last_num = num
					last_ans = cnt(num * num, arr2)
					ans += last_ans
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def find(self, nums, target):
		seen = collections.defaultdict(int)
		res = 0
		for i in nums:
			if target % i == 0 and target / i in seen:
				res += seen[target / i]
			seen[i] += 1
		return res

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for i in nums1:
			target = i * i
			res += self.find(nums2, target)
		for i in nums2:
			target = i * i
			res += self.find(nums1, target)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			res = 0
			for num in nums1:
				val = num ** 2
				dic = collections.defaultdict(int)
				for e in nums2:
					res += dic[e]
					dic[val / e] += 1
			return res
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		num12 = [x * x for x in nums1]
		num22 = [x * x for x in nums2]
		ans = 0
		for j2 in num22:
			c2 = Counter()
			for i in nums1:
				if j2 % i == 0:
					ans += c2[i]
					c2[j2 // i] += 1
		for j1 in num12:
			c1 = Counter()
			for i in nums2:
				if j1 % i == 0:
					ans += c1[i]
					c1[j1 // i] += 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = len(nums1)
		n2 = len(nums2)
		res = 0
		for i in range(n1):
			x = nums1[i] ** 2
			mp = defaultdict(int)
			for j in range(n2):
				if x % nums2[j] == 0:
					y = x // nums2[j]
					if y in mp:
						res += mp[y]
				mp[nums2[j]] += 1
		for i in range(n2):
			x = nums2[i] ** 2
			mp = defaultdict(int)
			for j in range(n1):
				if x % nums1[j] == 0:
					y = x // nums1[j]
					if y in mp:
						res += mp[y]
				mp[nums1[j]] += 1
		return res


from collections import Counter
from math import sqrt

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def is_perfect(x):
			return int(sqrt(x)) ** 2 == x
		(size1, size2) = (len(nums1), len(nums2))
		(count1, count2) = (Counter(nums1), Counter(nums2))
		(max1, max2) = (max(nums1), max(nums2))
		nums1.sort()
		nums2.sort()
		res = 0
		for i in range(size2):
			if nums2[i] > max1:
				break
			for j in range(i + 1, size2):
				mul = nums2[i] * nums2[j]
				if is_perfect(mul):
					res += count1[int(sqrt(mul))]
		for i in range(size1):
			if nums1[i] > max2:
				break
			for j in range(i + 1, size1):
				mul = nums1[i] * nums1[j]
				if is_perfect(mul):
					res += count2[int(sqrt(mul))]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		d1 = collections.defaultdict(int)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				sqr = math.sqrt(nums1[i] * nums1[j])
				if sqr == int(sqr):
					d1[int(sqr)] += 1
		for i in nums2:
			if i in d1:
				res += d1[i]
		d2 = collections.defaultdict(int)
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				sqr = math.sqrt(nums2[i] * nums2[j])
				if sqr == int(sqr):
					d2[int(sqr)] += 1
		for i in nums1:
			if i in d2:
				res += d2[i]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		prod1 = {}
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] not in prod1.keys():
					prod1[nums1[i] * nums1[j]] = 1
				else:
					prod1[nums1[i] * nums1[j]] += 1
		prod2 = {}
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] not in prod2.keys():
					prod2[nums2[i] * nums2[j]] = 1
				else:
					prod2[nums2[i] * nums2[j]] += 1
		cnt = 0
		for i in nums1:
			if i * i in prod2.keys():
				cnt += prod2[i * i]
		for i in nums2:
			if i * i in prod1.keys():
				cnt += prod1[i * i]
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		result = 0
		dic1 = {}
		dic2 = {}
		for x in nums1:
			if x not in dic1:
				dic1[x] = 0
			dic1[x] += 1
		for x in nums2:
			if x not in dic2:
				dic2[x] = 0
			dic2[x] += 1
		for (k, v) in dic1.items():
			for (k1, v1) in dic2.items():
				if k1 < k:
					if k ** 2 % k1 == 0:
						if k ** 2 / k1 in dic2:
							result += v * v1 * dic2[k ** 2 / k1]
				elif k1 == k:
					result += v * v1 * (v1 - 1) / 2
		for (k, v) in dic2.items():
			for (k1, v1) in dic1.items():
				if k1 < k:
					if k ** 2 % k1 == 0:
						if k ** 2 / k1 in dic1:
							result += v * v1 * dic1[k ** 2 / k1]
				elif k1 == k:
					result += v * v1 * (v1 - 1) / 2
		return int(result)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(nums1, nums2):
			triplets = 0
			cnt2 = {}
			for (i2, num2) in enumerate(nums2):
				if num2 not in cnt2:
					cnt2[num2] = []
				cnt2[num2].append(i2)
			for (i1, num1) in enumerate(nums1):
				square = num1 ** 2
				for (num2j, idxs2j) in cnt2.items():
					if square % num2j != 0:
						continue
					num2k = int(square // num2j)
					if num2k not in cnt2:
						continue
					idxs2k = cnt2[num2k]
					combined = []
					for idx2j in idxs2j:
						combined.append((idx2j, 0))
					for idx2k in idxs2k:
						combined.append((idx2k, 1))
					combined.sort()
					temp_cnt = 0
					for comb in combined:
						(idx, ty) = comb
						if ty == 0:
							triplets += temp_cnt
						else:
							temp_cnt += 1
			return triplets
		triplets1 = count(nums1, nums2)
		triplets2 = count(nums2, nums1)
		return triplets1 + triplets2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def comb(nums, k):
			res = 0
			count = collections.defaultdict(int)
			for i in range(len(nums)):
				x = nums[i]
				y = k * k // x
				if x * y == k * k:
					res += count[y]
				count[x] += 1
			return res
		res = 0
		for x in nums1:
			res += comb(nums2, x)
		for x in nums2:
			res += comb(nums1, x)
		return res


class Solution:

	def formMulitplication(s, a):
		n = len(a)
		square_nums = []
		for i in range(n - 1):
			for j in range(i + 1, n):
				p = a[i] * a[j]
				sqrt_p = int(sqrt(p))
				if sqrt_p * sqrt_p == p:
					square_nums.append(sqrt_p)
		return square_nums

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		countnums1 = [0 for i in range(100000 + 1)]
		countnums2 = [0 for i in range(100000 + 1)]
		for i in range(len(nums1)):
			countnums1[nums1[i]] += 1
		for i in range(len(nums2)):
			countnums2[nums2[i]] += 1
		square_nums1 = self.formMulitplication(nums1)
		result_type1 = 0
		for i in range(len(square_nums1)):
			result_type1 += countnums2[square_nums1[i]]
		square_nums2 = self.formMulitplication(nums2)
		result_type2 = 0
		for i in range(len(square_nums2)):
			result_type2 += countnums1[square_nums2[i]]
		return result_type1 + result_type2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = defaultdict(list)
		d2 = defaultdict(list)
		for (i, x) in enumerate(nums1):
			for (j, y) in enumerate(nums1):
				if j <= i:
					continue
				r = int(sqrt(x * y))
				if r ** 2 == x * y:
					d1[r].append((i, j))
		for (i, x) in enumerate(nums2):
			for (j, y) in enumerate(nums2):
				if j <= i:
					continue
				r = int(sqrt(x * y))
				if r ** 2 == x * y:
					d2[r].append((i, j))
		ret = 0
		for i in nums1:
			ret += len(d2[i])
		for i in nums2:
			ret += len(d1[i])
		return ret


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(nums1, nums2):
			res = 0
			for i in nums1:
				map1 = defaultdict(int)
				sq = i ** 2
				for j in nums2:
					comp = sq / j
					if j in map1:
						res += map1[j]
					map1[comp] += 1
			return res
		return count(nums1, nums2) + count(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		set1 = collections.defaultdict(set)
		for (i, num) in enumerate(nums1):
			set1[num].add(i)
		set2 = collections.defaultdict(set)
		for (i, num) in enumerate(nums2):
			set2[num].add(i)
		res = 0
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if (nums2[i] * nums2[j]) ** 0.5 == int((nums2[i] * nums2[j]) ** 0.5):
					m = int((nums2[i] * nums2[j]) ** 0.5)
					if m in set1:
						res += len(set1[m])
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if (nums1[i] * nums1[j]) ** 0.5 == int((nums1[i] * nums1[j]) ** 0.5):
					m = int((nums1[i] * nums1[j]) ** 0.5)
					if m in set2:
						res += len(set2[m])
		return res


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def solv(A, B):
			ans = 0
			for a in A:
				x = a ** 2
				seen = defaultdict(lambda : 0)
				for b in B:
					(q, r) = divmod(x, b)
					if r != 0:
						seen[b] += 1
						continue
					ans += seen[q]
					seen[b] += 1
			return ans
		return solv(nums1, nums2) + solv(nums2, nums1)


from itertools import combinations

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def isPerSq(n):
			return int(math.sqrt(n) + 0.5) ** 2 == n
		d1 = Counter(nums1)
		d2 = Counter(nums2)
		s = 0
		for (x, y) in combinations(nums2, 2):
			if isPerSq(x * y):
				s += d1[math.sqrt(x * y)]
		for (x, y) in combinations(nums1, 2):
			if isPerSq(x * y):
				s += d2[math.sqrt(x * y)]
		return s


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def generate_nums(nums):
			nums = sorted(list(collections.Counter(nums).items()))
			n = len(nums)
			pow_nums = defaultdict(int)
			mul_nums = defaultdict(int)
			for i in range(n):
				num = nums[i][0]
				pow_nums[num * num] += nums[i][1]
				for j in range(i + 1, n):
					mul_nums[num * nums[j][0]] += nums[i][1] * nums[j][1]
				mul_nums[num * num] += nums[i][1] * (nums[i][1] - 1) // 2
			return (pow_nums, mul_nums)
		(pow_nums1, mul_nums1) = generate_nums(nums1)
		(pow_nums2, mul_nums2) = generate_nums(nums2)
		ans = 0

		def check_triplet(nums, pow_nums):
			ans = 0
			for (num, count) in nums.items():
				ans += pow_nums[num] * count
			return ans
		ans += check_triplet(mul_nums1, pow_nums2)
		ans += check_triplet(mul_nums2, pow_nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		p1 = {}
		p2 = {}
		c = 0
		for i in range(len(nums1)):
			for j in range(len(nums1)):
				if i != j:
					p1[nums1[i] * nums1[j]] = p1.get(nums1[i] * nums1[j], 0) + 1
		for i in range(len(nums2)):
			for j in range(len(nums2)):
				if i != j:
					p2[nums2[i] * nums2[j]] = p2.get(nums2[i] * nums2[j], 0) + 1
		for i in nums1:
			if i * i in list(p2.keys()):
				c += p2[i * i] // 2
		for i in nums2:
			if i * i in list(p1.keys()):
				c += p1[i * i] // 2
		return c


import itertools, math
from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def is_perfect_square(n):
			return int(math.sqrt(n) + 0.5) ** 2 == n
		(nums1_cntr, nums2_cntr) = (Counter(nums1), Counter(nums2))
		s = 0
		for (x, y) in itertools.combinations(nums2, 2):
			if is_perfect_square(x * y):
				s += nums1_cntr[math.sqrt(x * y)]
		for (x, y) in itertools.combinations(nums1, 2):
			if is_perfect_square(x * y):
				s += nums2_cntr[math.sqrt(x * y)]
		return s


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		for n in nums1:
			n2 = n * n
			seen = collections.defaultdict(int)
			for i in range(len(nums2)):
				ans += seen[n2 / nums2[i]]
				seen[nums2[i]] += 1
		for n in nums2:
			n2 = n * n
			seen = collections.defaultdict(int)
			for i in range(len(nums1)):
				ans += seen[n2 / nums1[i]]
				seen[nums1[i]] += 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		nums1square = []
		for i in nums1:
			nums1square.append(i * i)
		for i in nums1square:
			d = dict()
			for j in nums2:
				if i % j == 0:
					if i / j in d.keys():
						ans += d[i / j]
					if j in d.keys():
						d[j] += 1
					else:
						d[j] = 1
		nums2square = []
		for i in nums2:
			nums2square.append(i * i)
		for i in nums2square:
			d = dict()
			for j in nums1:
				if i % j == 0:
					if i / j in d.keys():
						ans += d[i / j]
					if j in d.keys():
						d[j] += 1
					else:
						d[j] = 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		if len(nums1) == 1 and len(nums2) == 1:
			return 0
		if set(nums1) == set(nums2) and len(set(nums1)) == 1:
			res = len(nums2) * (len(nums2) - 1) // 2
			res = res * len(nums1)
			res = res + len(nums1) * (len(nums1) - 1) // 2 * len(nums2)
			return res
		m1 = self.getmultiply(nums1)
		m2 = self.getmultiply(nums2)
		for x in nums1:
			if x * x in m2:
				res = res + len(m2[x * x])
		for y in nums2:
			if y * y in m1:
				res = res + len(m1[y * y])
		return res

	def getmultiply(self, nums):
		res = {}
		for x in range(len(nums)):
			for y in range(x + 1, len(nums)):
				if nums[x] * nums[y] in res and [x, y]:
					res[nums[x] * nums[y]].append([x, y])
				else:
					res[nums[x] * nums[y]] = [[x, y]]
		return res

	def getsq(self, nums):
		res = {}
		for x in range(len(nums)):
			if nums[x] * nums[x] in res:
				if x not in res[nums[x] * nums[x]]:
					res[nums[x] * nums[x]].append(x)
			else:
				res[nums[x] * nums[x]] = [x]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		cnt = 0
		for num in nums1:
			target = num * num
			cnt += self.twoProduct(nums2, target)
		for num2 in nums2:
			target2 = num2 * num2
			cnt += self.twoProduct(nums1, target2)
		return cnt

	def twoProduct(self, nums, target):
		cnt = 0
		hashmap = collections.defaultdict(int)
		for i in range(len(nums)):
			if target / nums[i] in hashmap:
				cnt += hashmap[target / nums[i]]
			hashmap[nums[i]] += 1
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = {}
		d2 = {}
		for i in nums1:
			d1[i] = d1.get(i, 0) + 1
		for i in nums2:
			d2[i] = d2.get(i, 0) + 1
		ans = 0
		d3 = {}
		print(d1, d2)
		for i in range(len(nums1)):
			d3 = {}
			for j in range(len(nums2)):
				if nums1[i] * nums1[i] % nums2[j] == 0:
					x = nums1[i] * nums1[i] // nums2[j]
					y = nums2[j]
					if d3.get((x, y), -1) == -1:
						if x == y:
							x1 = d2.get(x, 0)
							ans += x1 * (x1 - 1) // 2
							d3[x, y] = 1
						else:
							ans += d2.get(x, 0) * d2.get(y, 0)
							d3[x, y] = 1
							d3[y, x] = 1
		d4 = {}
		for i in range(len(nums2)):
			d4 = {}
			for j in range(len(nums1)):
				if nums2[i] * nums2[i] % nums1[j] == 0:
					x = nums2[i] * nums2[i] // nums1[j]
					y = nums1[j]
					if d4.get((x, y), -1) == -1:
						if x == y:
							x1 = d1.get(x, 0)
							ans += x1 * (x1 - 1) // 2
							d4[x, y] = 1
						else:
							ans += d1.get(x, 0) * d1.get(y, 0)
							d4[x, y] = 1
							d4[y, x] = 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cnt(tot, arr):
			mp = {}
			ans = 0
			for val in arr:
				if tot % val == 0 and tot / val in mp:
					ans += mp[tot / val]
				mp[val] = mp.get(val, 0) + 1
			return ans
		ans = 0
		for num in nums1:
			ans += cnt(num * num, nums2)
		for num in nums2:
			ans += cnt(num * num, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1, nums2):
		(mp1, mp2) = ({}, {})
		for ele in nums1:
			if ele in mp1:
				mp1[ele] += 1
			else:
				mp1[ele] = 1
		for ele in nums2:
			if ele in mp2:
				mp2[ele] += 1
			else:
				mp2[ele] = 1
		ans = 0
		for (k1, v1) in mp1.items():
			tar = k1 ** 2
			for k2 in sorted(mp2.keys()):
				if k2 ** 2 > tar:
					break
				elif k2 ** 2 == tar:
					ans += v1 * mp2[k2] * (mp2[k2] - 1) // 2
				elif tar % k2 == 0 and tar // k2 in mp2:
					ans += v1 * mp2[k2] * mp2[tar // k2]
		for (k2, v2) in mp2.items():
			tar = k2 ** 2
			for k1 in sorted(mp1.keys()):
				if k1 ** 2 > tar:
					break
				elif k1 ** 2 == tar:
					ans += v2 * mp1[k1] * (mp1[k1] - 1) // 2
				elif tar % k1 == 0 and tar // k1 in mp1:
					ans += v2 * mp1[k1] * mp1[tar // k1]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		for num in nums1:
			ans += self.find_num_pairs(num, nums2)
		for num in nums2:
			ans += self.find_num_pairs(num, nums1)
		return ans

	def find_num_pairs(self, num, pair_list):
		pair_dict = {}
		square_num = num ** 2
		ans = 0
		for (i, n) in enumerate(pair_list):
			if square_num // n in pair_dict and square_num % n == 0:
				ans += len(pair_dict[square_num // n])
			if n not in pair_dict:
				pair_dict[n] = []
			pair_dict[n].append(i)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		s1 = collections.Counter()
		for n1 in nums1:
			s2 = collections.Counter()
			for n2 in nums2:
				if n1 * n1 % n2 == 0 and n1 * n1 // n2 in s2:
					res += s2[n1 * n1 // n2]
				if n2 * n2 % n1 == 0 and n2 * n2 // n1 in s1:
					res += s1[n2 * n2 // n1]
				s2[n2] += 1
			s1[n1] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for ele in nums1:
			res += self.twoProduct(ele * ele, nums2)
		for ele in nums2:
			res += self.twoProduct(ele * ele, nums1)
		return res

	def twoProduct(self, prod, nums):
		d = {}
		n = len(nums)
		res = 0
		for i in range(n):
			if prod % nums[i] == 0 and prod // nums[i] in d:
				res += d[prod // nums[i]]
			if nums[i] in d:
				d[nums[i]] += 1
			else:
				d[nums[i]] = 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1 = sorted(nums1)
		nums2 = sorted(nums2)
		count = 0
		for item in nums1:
			count += self.get_equal_square(item * item, nums2)
		for item in nums2:
			count += self.get_equal_square(item * item, nums1)
		return count

	def get_equal_square(self, val, arr):
		count = 0
		m = {}
		for (i, item) in enumerate(arr):
			if val % item:
				continue
			tmp = val / item
			if m.get(tmp, None):
				count += m.get(tmp)
			m[item] = m.get(item, 0) + 1
		return count


from collections import Counter
import math

class Solution:

	def f(self, nums1, nums2):
		n1 = len(nums1)
		freq_dict_2 = Counter(nums2)
		answer = 0
		for (pos_a, a) in enumerate(nums1):
			for pos_b in range(pos_a + 1, n1):
				b = nums1[pos_b]
				c_square = a * b
				potential_c = math.floor(math.sqrt(c_square))
				if potential_c ** 2 == c_square:
					if potential_c in freq_dict_2:
						answer += freq_dict_2[potential_c]
		return answer

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		final_answer = 0
		final_answer += self.f(nums1, nums2)
		final_answer += self.f(nums2, nums1)
		return final_answer


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def c(nums1, nums2):
			ans = 0
			for num in nums1:
				count = defaultdict(int)
				for i in range(len(nums2)):
					if nums2[i] in count:
						ans += count[nums2[i]]
					new = num * num
					if new % nums2[i] == 0:
						count[new // nums2[i]] += 1
			return ans
		ans = c(nums1, nums2) + c(nums2, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		for i in range(len(nums1)):
			h1 = {}
			target = nums1[i] * nums1[i]
			for j in range(len(nums2)):
				if target / nums2[j] in h1:
					ans += h1[target / nums2[j]]
				if nums2[j] in h1:
					h1[nums2[j]] += 1
				else:
					h1[nums2[j]] = 1
		for i in range(len(nums2)):
			h2 = {}
			target = nums2[i] * nums2[i]
			for j in range(len(nums1)):
				if target / nums1[j] in h2:
					ans += h2[target / nums1[j]]
				if nums1[j] in h2:
					h2[nums1[j]] += 1
				else:
					h2[nums1[j]] = 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		for num1 in nums1:
			a = num1 * num1
			hashSet = defaultdict(int)
			for num2 in nums2:
				complement = a / num2
				if complement in hashSet:
					count += hashSet[complement]
				hashSet[num2] += 1
		for num2 in nums2:
			a = num2 * num2
			hashSet = defaultdict(int)
			for num1 in nums1:
				complement = a / num1
				if complement in hashSet:
					count += hashSet[complement]
				hashSet[num1] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.calc(nums1, nums2) + self.calc(nums2, nums1)

	def calc(self, nums1, nums2):
		(d, ans) = (defaultdict(int), 0)
		for num in nums2:
			d[num] += 1
		for (i, num1) in enumerate(nums1):
			visited = {num: False for num in d}
			for num2 in d:
				cnt2 = d[num2]
				if visited[num2]:
					continue
				if num1 * num1 % num2 == 0 and num1 * num1 // num2 in d:
					(num3, cnt3) = (num1 * num1 // num2, d[num1 * num1 // num2])
					ans += cnt2 * cnt3 if num2 != num3 else cnt2 * (cnt2 - 1) // 2
					visited[num3] = True
					visited[num2] = True
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProduct(list1, list2, target):
			res = 0
			counter = collections.defaultdict(int)
			for j in range(len(list2)):
				(q, r) = divmod(target, list2[j])
				if r == 0 and q in counter:
					res += counter[q]
				counter[list2[j]] += 1
			return res
		res = 0
		for n in nums1:
			res += twoProduct(nums1, nums2, n ** 2)
		for n in nums2:
			res += twoProduct(nums2, nums1, n ** 2)
		return res


import sys
input = sys.stdin.readline
from collections import *

class Solution:

	def calc(self, l1, l2):
		cnt = Counter(l2)
		res = 0
		for i in range(len(l1)):
			for j in range(len(l2)):
				if l1[i] * l1[i] % l2[j] == 0:
					k = l1[i] * l1[i] // l2[j]
					res += cnt[k]
					if l2[j] == k:
						res -= 1
		return res // 2

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.calc(nums1, nums2) + self.calc(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		fin = 0
		for n in nums1:
			sq = n * n
			res = {}
			ans = defaultdict(list)
			for (i, x) in enumerate(nums2):
				y = sq / x
				if y in ans:
					fin += len(ans[y])
				ans[x].append(i)
		for n in nums2:
			sq = n * n
			res = set()
			ans = defaultdict(list)
			for (i, x) in enumerate(nums1):
				y = sq / x
				if y in ans:
					fin += len(ans[y])
				ans[x].append(i)
		return fin


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		d1 = collections.defaultdict(int)
		l1 = [i ** 2 for i in nums1]
		for i in range(len(nums2)):
			if nums2[i] in d1:
				res += d1[nums2[i]]
			for j in range(len(l1)):
				if l1[j] % nums2[i] == 0:
					d1[l1[j] // nums2[i]] += 1
		d2 = collections.defaultdict(int)
		l2 = [i ** 2 for i in nums2]
		for i in range(len(nums1)):
			if nums1[i] in d2:
				res += d2[nums1[i]]
			for j in range(len(l2)):
				if l2[j] % nums1[i] == 0:
					d2[l2[j] // nums1[i]] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(ind1, ind2) = (defaultdict(list), defaultdict(list))
		for (i, v) in enumerate(nums1):
			ind1[v].append(i)
		for (i, v) in enumerate(nums2):
			ind2[v].append(i)
		(type1, type2) = (0, 0)
		for (i, v) in enumerate(nums1):
			for (j, v2) in enumerate(nums2):
				if v * v % v2:
					continue
				req = v * v // v2
				type1 += len(ind2[req]) - (v2 == req)
		for (i, v) in enumerate(nums2):
			for v1 in nums1:
				if v * v % v1:
					continue
				req = v * v // v1
				type2 += len(ind1[req]) - (v1 == req)
		print(type1, type2)
		ans = type1 // 2 + type2 // 2
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		for x in nums1:
			seen = {}
			v = x * x
			for i in nums2:
				if i in seen:
					count += seen[i]
				seen[v / i] = seen.get(v / i, 0) + 1
		for x in nums2:
			seen = {}
			v = x * x
			for i in nums1:
				if i in seen:
					count += seen[i]
				seen[v / i] = seen.get(v / i, 0) + 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.check_list(nums1, nums2) + self.check_list(nums2, nums1)

	def check_list(self, nums1, nums2):
		count = 0
		for value in nums1:
			target = value ** 2
			count += self.find_two_sum(nums2, target)
		return count

	def find_two_sum(self, nums, target):
		found = dict()
		count = 0
		for (idx, num) in enumerate(nums):
			if target % num != 0:
				continue
			search_val = target // num
			if search_val in found.keys():
				count += len(found[search_val])
			if num in found.keys():
				found[num].append(idx)
			else:
				found[num] = [idx]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			target = [i ** 2 for i in nums1]
			ans = 0
			for i in range(len(target)):
				s = target[i]
				d = collections.defaultdict(list)
				for j in range(len(nums2)):
					if nums2[j] in d:
						ans += len(d[nums2[j]])
					d[s / nums2[j]].append(j)
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		tmp_dict1 = dict()
		res = 0
		for (i, v) in enumerate(nums1):
			if v not in tmp_dict1:
				tmp_dict1[v] = self.get_num_tr(v, nums2)
			res += tmp_dict1.get(v)
		tmp_dict2 = dict()
		for (i, v) in enumerate(nums2):
			if v not in tmp_dict2:
				tmp_dict2[v] = self.get_num_tr(v, nums1)
			res += tmp_dict2.get(v)
		return res

	def get_num_tr(self, num, nums):
		n = num * num
		res = 0
		dct = dict()
		for (i, v) in enumerate(nums):
			if n % v == 0:
				res += dct.get(int(n / v), 0)
			dct[v] = dct.get(v, 0) + 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.triplets(nums1, nums2) + self.triplets(nums2, nums1)

	def triplets(self, nums1, nums2):
		nums1_sq = [x * x for x in nums1]
		n_triplets = 0
		for i in range(len(nums1_sq)):
			nums2_lookup = {}
			for j in range(len(nums2)):
				if nums1_sq[i] % nums2[j] != 0:
					continue
				num_to_look_for = nums1_sq[i] / nums2[j]
				count = nums2_lookup.get(num_to_look_for, 0)
				n_triplets += count
				if nums2[j] in nums2_lookup:
					nums2_lookup[nums2[j]] += 1
				else:
					nums2_lookup[nums2[j]] = 1
		return n_triplets


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def get_prod_dic(arr, num_dic):
			i = 0
			while i < len(arr):
				j = i + 1
				while j < len(arr):
					p = arr[i] * arr[j]
					if p not in num_dic:
						num_dic[p] = []
					num_dic[p].append([i, j])
					j += 1
				i += 1
			return
		n1_dic = {}
		get_prod_dic(nums1, n1_dic)
		n2_dic = {}
		get_prod_dic(nums2, n2_dic)
		count = 0
		for n in nums1:
			p = n * n
			if p in n2_dic:
				count += len(n2_dic[p])
		for n in nums2:
			p = n * n
			if p in n1_dic:
				count += len(n1_dic[p])
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		dic1 = {}
		dic2 = {}
		for (i, e) in enumerate(nums1):
			target = e ** 2
			for j in range(len(nums2)):
				if target % nums2[j] == 0:
					if nums2[j] in dic1:
						res += dic1[nums2[j]]
					dic1[target // nums2[j]] = dic1.get(target // nums2[j], 0) + 1
			dic1 = {}
		for (i, e) in enumerate(nums2):
			target = e ** 2
			for j in range(len(nums1)):
				if target % nums1[j] == 0:
					if nums1[j] in dic2:
						res += dic2[nums1[j]]
					dic2[target // nums1[j]] = dic2.get(target // nums1[j], 0) + 1
			dic2 = {}
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import Counter
		c1 = Counter(nums1)
		c2 = Counter(nums2)
		ans = 0
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				if math.sqrt(nums2[j] * nums2[k]) in c1:
					ans += c1[math.sqrt(nums2[j] * nums2[k])]
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				if math.sqrt(nums1[j] * nums1[k]) in c2:
					ans += c2[math.sqrt(nums1[j] * nums1[k])]
		return ans


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(c1, c2) = (Counter(nums1), Counter(nums2))
		(n, m) = (len(nums1), len(nums2))
		ans = 0
		for i in range(n):
			for j in range(m):
				nums2_k = nums1[i] * nums1[i] / nums2[j]
				ans += c2[nums2_k]
				if nums2_k == nums2[j]:
					ans -= 1
		for i in range(m):
			for j in range(n):
				nums1_k = nums2[i] * nums2[i] / nums1[j]
				ans += c1[nums1_k]
				if nums1_k == nums1[j]:
					ans -= 1
		return ans // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		D = {}
		G = {}
		H = {}
		N1 = {}
		N2 = {}
		for i in range(len(nums1)):
			N1[nums1[i]] = 1
			for j in range(i + 1, len(nums1)):
				D[nums1[i] * nums1[j]] = 1
		for i in range(len(nums2)):
			N2[nums2[i]] = 1
			for j in range(i + 1, len(nums2)):
				G[nums2[i] * nums2[j]] = 1
		for i in range(len(nums1)):
			if nums1[i] ** 2 in G:
				if nums1[i] ** 2 not in H:
					tmp = 0
					for x in range(len(nums2)):
						if nums1[i] ** 2 % nums2[x] == 0 and nums1[i] ** 2 // nums2[x] in N2:
							for y in range(x + 1, len(nums2)):
								if nums2[x] * nums2[y] == nums1[i] ** 2:
									tmp += 1
					H[nums1[i] ** 2] = tmp
					ans += tmp
				else:
					ans += H[nums1[i] ** 2]
		H = {}
		for i in range(len(nums2)):
			if nums2[i] ** 2 in D:
				if nums2[i] ** 2 not in H:
					tmp = 0
					for x in range(len(nums1)):
						if nums2[i] ** 2 % nums1[x] == 0 and nums2[i] ** 2 // nums1[x] in N1:
							for y in range(x + 1, len(nums1)):
								if nums1[x] * nums1[y] == nums2[i] ** 2:
									tmp += 1
					H[nums2[i] ** 2] = tmp
					ans += tmp
				else:
					ans += H[nums2[i] ** 2]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(A, B):
			res = 0
			n1 = len(A)
			n2 = len(B)
			for i in range(n1):
				target = A[i] ** 2
				d = collections.defaultdict(int)
				for num in B:
					if target / num in d:
						res += d[target / num]
					d[num] += 1
			return res
		return count(nums1, nums2) + count(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(cnt1, cnt2) = (collections.Counter(nums1), collections.Counter(nums2))
		ans = 0
		for (v1, l1) in list(cnt1.items()):
			for (v2, l2) in list(cnt2.items()):
				if v2 != v1 and v1 ** 2 / v2 in cnt2:
					ans += l1 * l2 * cnt2[v1 ** 2 / v2]
				elif v2 == v1:
					ans += l1 * l2 * (l2 - 1)
		for (v1, l1) in list(cnt2.items()):
			for (v2, l2) in list(cnt1.items()):
				if v2 != v1 and v1 ** 2 / v2 in cnt1:
					ans += l1 * l2 * cnt1[v1 ** 2 / v2]
				elif v2 == v1:
					ans += l1 * l2 * (l2 - 1)
		return int(ans / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for i in range(len(nums1)):
			target = nums1[i] ** 2
			prev = collections.Counter()
			for j in range(len(nums2)):
				if target % nums2[j] != 0:
					continue
				val = target // nums2[j]
				if val in prev:
					res += prev[val]
				prev[nums2[j]] += 1
		for i in range(len(nums2)):
			target = nums2[i] ** 2
			prev = collections.Counter()
			for j in range(len(nums1)):
				if target % nums1[j] != 0:
					continue
				val = target // nums1[j]
				if val in prev:
					res += prev[val]
				prev[nums1[j]] += 1
		return res


class Solution:

	def numTriplets(self, a: List[int], b: List[int]) -> int:
		n = len(a)
		m = len(b)
		pro1 = {}
		pro2 = {}
		for i in range(n):
			for j in range(n):
				if i != j:
					pro1[a[i] * a[j]] = pro1[a[i] * a[j]] + 1 if a[i] * a[j] in pro1 else 1
		for i in range(m):
			for j in range(m):
				if i != j:
					pro2[b[i] * b[j]] = pro2[b[i] * b[j]] + 1 if b[i] * b[j] in pro2 else 1
		ans = 0
		for i in range(n):
			if a[i] ** 2 in pro2:
				ans += pro2[a[i] ** 2] // 2
		for i in range(m):
			if b[i] ** 2 in pro1:
				ans += pro1[b[i] ** 2] // 2
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(l1, l2):
			ans = 0
			for e in l1:
				dp = Counter()
				tar = e ** 2
				for x in l2:
					if tar % x == 0:
						ans += dp[tar // x]
					dp[x] += 1
			return ans
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		A = collections.defaultdict(int)
		B = collections.defaultdict(int)
		ans = 0
		for i in nums1:
			a = i * i
			B.clear()
			for j in nums2:
				b = j * j
				x = a / j
				if x in B:
					ans += B[x]
				y = b / i
				if y in A:
					ans += A[y]
				B[j] += 1
			A[i] += 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cal(nums1, nums2):
			ans = 0
			for a in nums1:
				d = collections.defaultdict(lambda : 0)
				sq = a * a
				for ib in range(0, len(nums2)):
					b = nums2[ib]
					if b == 0:
						if a == 0:
							ans += ib
						else:
							continue
					if sq % b != 0:
						continue
					else:
						c = sq / b
						if c in d:
							ans += d[c]
					d[b] += 1
			print(ans)
			return ans
		return cal(nums1, nums2) + cal(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums1, nums2):
			s = [n * n for n in nums1]
			count = 0
			d = collections.defaultdict(list)
			for i in range(len(nums2)):
				d[nums2[i]].append(i)
			for n in s:
				for i in range(len(nums2)):
					if n % nums2[i] == 0 and n // nums2[i] in d:
						if nums2[i] == n // nums2[i]:
							count += len(d[n // nums2[i]]) - 1
						else:
							count += len(d[n // nums2[i]])
			return count // 2
		return helper(nums1, nums2) + helper(nums2, nums1)


from collections import Counter
from itertools import combinations
from math import sqrt

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = Counter(nums1)
		count2 = Counter(nums2)
		set1 = set(nums1)
		set2 = set(nums2)
		nums11 = list([x * x for x in set1])
		nums22 = list([x * x for x in set2])
		count = 0
		for (i, j) in list(combinations(set1, 2)):
			if i * j in nums22:
				count += count2[sqrt(i * j)] * count1[i] * count1[j]
		for (i, j) in list(combinations(set2, 2)):
			if i * j in nums11:
				count += count1[sqrt(i * j)] * count2[i] * count2[j]
		for i in set1:
			if count1[i] > 1 and i * i in nums22:
				count += count1[i] * (count1[i] - 1) * count2[i] // 2
		for i in set2:
			if count2[i] > 1 and i * i in nums11:
				count += count2[i] * (count2[i] - 1) * count1[i] // 2
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(l1, l2):
			res = 0
			for i in range(len(l1)):
				comp = dict()
				target = l1[i] ** 2
				for j in range(len(l2)):
					if target / l2[j] in comp:
						res += comp[target / l2[j]]
					comp[l2[j]] = comp.get(l2[j], 0) + 1
			return res
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		nums1.sort()
		nums2.sort()
		for i in range(len(nums2)):
			ii = nums2[i] ** 2
			ar = {}
			for j in range(len(nums1)):
				if ii % nums1[j] == 0:
					g = ii // nums1[j]
				else:
					ar[nums1[j]] = ar.get(nums1[j], 0) + 1
					continue
				if ar.get(g) is not None:
					ans += ar[g]
				ar[nums1[j]] = ar.get(nums1[j], 0) + 1
		for i in range(len(nums1)):
			ii = nums1[i] ** 2
			ar = {}
			for j in range(len(nums2)):
				if ii % nums2[j] == 0:
					g = ii // nums2[j]
				else:
					ar[nums2[j]] = ar.get(nums2[j], 0) + 1
					continue
				if ar.get(g) is not None:
					ans += ar[g]
				ar[nums2[j]] = ar.get(nums2[j], 0) + 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def lowerbound(target, left, right, nums):
			while left < right:
				mid = left + (right - left) // 2
				if nums[mid] == target:
					right = mid
				elif nums[mid] < target:
					left = mid + 1
				else:
					right = mid
			return left

		def higherbound(target, left, right, nums):
			while left < right:
				mid = left + (right - left) // 2
				if nums[mid] == target:
					left = mid + 1
				elif nums[mid] < target:
					left = mid + 1
				else:
					right = mid
			return left

		@lru_cache(maxsize=None)
		def helper1(n):
			result = 0
			for i in range(len(nums1)):
				if n % nums1[i] != 0:
					continue
				target = n // nums1[i]
				lower = lowerbound(target, i + 1, len(nums1), nums1)
				higher = higherbound(target, i + 1, len(nums1), nums1)
				result += higher - lower
			return result

		@lru_cache(maxsize=None)
		def helper2(n):
			result = 0
			for i in range(len(nums2)):
				if n % nums2[i] != 0:
					continue
				target = n // nums2[i]
				lower = lowerbound(target, i + 1, len(nums2), nums2)
				higher = higherbound(target, i + 1, len(nums2), nums2)
				result += higher - lower
			return result
		result = 0
		for n in nums1:
			result += helper2(n * n)
		for n in nums2:
			result += helper1(n * n)
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.triplets(nums1, nums2) + self.triplets(nums2, nums1)

	def triplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		counter = Counter(nums2)
		for i in range(len(nums1)):
			target = nums1[i] ** 2
			for j in range(len(nums2)):
				if target / nums2[j] in counter:
					if target / nums2[j] == nums2[j]:
						count += counter[target / nums2[j]] - 1
					else:
						count += counter[target / nums2[j]]
		return int(count / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		dic1 = {}
		dic2 = {}
		s1 = []
		s2 = []
		r = 0
		n1 = len(nums1)
		n2 = len(nums2)
		for i in range(n1):
			r += self.helper(nums1[i] * nums1[i], nums2)
		for i in range(n2):
			r += self.helper(nums2[i] * nums2[i], nums1)
		return r

	def helper(self, prod, arr):
		d = {}
		r = 0
		for i in range(len(arr)):
			if prod % arr[i] == 0:
				if prod // arr[i] in d:
					r += d[prod // arr[i]]
			d[arr[i]] = d.get(arr[i], 0) + 1
		return r


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(nums1, nums2):
			pairs = []
			(N1, N2) = (len(nums1), len(nums2))
			result = 0
			for i in range(N2):
				for j in range(i + 1, N2):
					pairs.append((nums2[i], nums2[j]))
			Ns = collections.Counter(nums1)
			for (u, v) in pairs:
				if (u * v) ** 0.5 in Ns:
					result += Ns[(u * v) ** 0.5]
			return result
		return count(nums1, nums2) + count(nums2, nums1)


from collections import Counter

class Solution:

	def search(self, nums1, nums2, counter):
		for i in range(len(nums1)):
			if nums1[i] ** 2 > nums2[-1] ** 2:
				break
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] > nums2[-1] ** 2:
					break
				target = nums1[i] * nums1[j]
				self.rst += counter[target]

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		if not nums1 or not nums2:
			return 0
		nums1.sort()
		nums2.sort()
		counter1 = Counter([x ** 2 for x in nums1])
		counter2 = Counter([x ** 2 for x in nums2])
		self.rst = 0
		self.search(nums1, nums2, counter2)
		self.search(nums2, nums1, counter1)
		return self.rst


from math import sqrt

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = [0] * 100001
		count2 = [0] * 100001
		for i in nums1:
			count1[i] += 1
		for i in nums2:
			count2[i] += 1
		m = len(nums1)
		n = len(nums2)
		ans = 0
		for i in range(m - 1):
			for j in range(i + 1, m):
				sq = int(sqrt(nums1[i] * nums1[j]))
				if sq ** 2 == nums1[i] * nums1[j]:
					ans += count2[sq]
		for i in range(n - 1):
			for j in range(i + 1, n):
				sq = int(sqrt(nums2[i] * nums2[j]))
				if sq ** 2 == nums2[i] * nums2[j]:
					ans += count1[sq]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ret1 = self.check(nums1, nums2)
		ret2 = self.check(nums2, nums1)
		return ret1 + ret2

	def check(self, n1: List[int], n2: List[int]):
		count_n2_org = Counter(n2)
		cnt = 0
		for i in range(len(n1)):
			square = n1[i] ** 2
			count_n2 = count_n2_org.copy()
			for j in range(len(n2)):
				if square % n2[j] == 0:
					target = square // n2[j]
					if count_n2[target] > 0:
						count_n2[n2[j]] -= 1
						cnt += count_n2[target]
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.helper(nums1, nums2) + self.helper(nums2, nums1)

	def helper(self, nums1, nums2):
		res = 0
		for n in nums1:
			cnt = {}
			for m in nums2:
				(q, d) = (n * n % m, n * n // m)
				if q == 0 and d > 0:
					if d in cnt:
						res += cnt[d]
					cnt[m] = cnt.get(m, 0) + 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import defaultdict
		count = 0
		Dict = defaultdict(int)
		for i in range(len(nums1)):
			num = nums1[i] * nums1[i]
			Dict.clear()
			for j in range(len(nums2)):
				if Dict[nums2[j]] > 0:
					count += Dict[nums2[j]]
				if num % nums2[j] == 0:
					x = num // nums2[j]
					Dict[x] += 1
		Dict.clear()
		for i in range(len(nums2)):
			num = nums2[i] * nums2[i]
			Dict.clear()
			for j in range(len(nums1)):
				if Dict[nums1[j]] > 0:
					count += Dict[nums1[j]]
				if num % nums1[j] == 0:
					x = num // nums1[j]
					Dict[x] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		dic1 = dict()
		for num in nums1:
			if num in dic1:
				dic1[num] += 1
			else:
				dic1[num] = 1
		dic2 = dict()
		for num in nums2:
			if num in dic2:
				dic2[num] += 1
			else:
				dic2[num] = 1
		for num1 in nums1:
			square = num1 ** 2
			for num2 in nums2:
				if square / num2 in dic2:
					if square / num2 == num2:
						count += dic2[square / num2] - 1
					else:
						count += dic2[square / num2]
		for num2 in nums2:
			square = num2 ** 2
			for num1 in nums1:
				if square / num1 in dic1:
					if square / num1 == num1:
						count += dic1[square / num1] - 1
					else:
						count += dic1[square / num1]
		return int(count / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = collections.Counter(nums1)
		count2 = collections.Counter(nums2)

		def cal(nums1, count2):
			ans = 0
			for n1 in nums1:
				sq = n1 ** 2
				for n2 in sorted(count2):
					if sq % n2 != 0 or sq // n2 not in count2:
						continue
					c2 = sq // n2
					if c2 < n2:
						break
					elif c2 == n2 and count2[n2] > 1:
						ans += math.comb(count2[n2], 2)
					elif c2 > n2:
						ans += count2[n2] * count2[c2]
			return ans
		return cal(nums1, count2) + cal(nums2, count1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProduct(n, nums):
			counter = collections.Counter()
			res = 0
			for num in nums:
				if n % num == 0:
					res += counter[n / num]
				counter[num] += 1
			return res
		res = 0
		for num in nums1:
			res += twoProduct(num * num, nums2)
		for num in nums2:
			res += twoProduct(num * num, nums1)
		return res


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def get_data(nums1, nums2):
			count = defaultdict(int)
			for i in range(len(nums2)):
				count[nums2[i]] += 1
			s = 0
			for i in range(len(nums1)):
				for j in range(len(nums2)):
					if nums1[i] * nums1[i] % nums2[j] != 0:
						continue
					elif nums2[j] == nums1[i] * nums1[i] // nums2[j]:
						s += count[nums1[i] * nums1[i] // nums2[j]] - 1
					else:
						s += count[nums1[i] * nums1[i] // nums2[j]]
			return s // 2
		return get_data(nums1, nums2) + get_data(nums2, nums1)


class Solution:

	def numTriplets(self, a: List[int], b: List[int]) -> int:

		def count(a, b):
			ret = 0
			for x in a:
				c = Counter()
				for y in b:
					square = x * x
					if square % y == 0:
						ret += c[square // y]
					c[y] += 1
			return ret
		return count(a, b) + count(b, a)


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:
		(countA, countB) = (Counter(A), Counter(B))
		res = 0
		for i in range(len(A)):
			x = A[i] * A[i]
			for j in range(len(B)):
				if x % B[j] == 0 and x // B[j] in countB:
					if B[j] * B[j] == x:
						res += countB[x // B[j]] - 1
					else:
						res += countB[x // B[j]]
		for i in range(len(B)):
			x = B[i] * B[i]
			for j in range(len(A)):
				if x % A[j] == 0 and x // A[j] in countA:
					if A[j] * A[j] == x:
						res += countA[x // A[j]] - 1
					else:
						res += countA[x // A[j]]
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		for a in nums1:
			sq = a * a
			cnt = Counter()
			for b in nums2:
				if sq % b == 0 and sq // b in cnt:
					res += cnt[sq // b]
				cnt[b] += 1
		for a in nums2:
			sq = a * a
			cnt = Counter()
			for b in nums1:
				if sq % b == 0 and sq // b in cnt:
					res += cnt[sq // b]
				cnt[b] += 1
		return res


class Solution:

	def numTriplets(self, nums1, nums2):
		res = 0
		for n in nums1:
			res += self.twoProduct(n * n, nums2)
		for n in nums2:
			res += self.twoProduct(n * n, nums1)
		return res

	def twoProduct(self, target, nums):
		count = 0
		compFreq = {}
		for i in range(len(nums)):
			comp = target / nums[i]
			if comp == int(comp):
				if nums[i] in compFreq:
					count += compFreq[nums[i]]
				if comp in compFreq:
					compFreq[comp] += 1
				else:
					compFreq[comp] = 1
		return count


from bisect import bisect_right
from collections import defaultdict

def sol(inp1, inp2):
	values1 = defaultdict(list)
	values2 = defaultdict(list)
	inp1.sort()
	inp2.sort()
	for (i1, v1) in enumerate(inp1):
		values1[v1].append(i1)
	for (i2, v2) in enumerate(inp2):
		values2[v2].append(i2)
	count = 0
	for (i1, v1) in enumerate(inp1):
		for (i2, v2) in enumerate(inp2):
			if v2 > v1:
				break
			matches = values2[v1 * v1 / v2]
			ins = bisect_right(matches, i2)
			count += len(matches) - ins
	for (i2, v2) in enumerate(inp2):
		for (i1, v1) in enumerate(inp1):
			if v1 > v2:
				break
			matches = values1[v2 * v2 / v1]
			ins = bisect_right(matches, i1)
			count += len(matches) - ins
	return count

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return sol(nums1, nums2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import defaultdict
		import math
		cnt1 = defaultdict(int)
		cnt2 = defaultdict(int)
		for k in range(len(nums1) - 1):
			for j in range(k + 1, len(nums1)):
				temp = nums1[k] * nums1[j]
				if temp - math.ceil(temp ** 0.5) ** 2 == 0:
					cnt1[temp] += 1
		for k in range(len(nums2) - 1):
			for j in range(k + 1, len(nums2)):
				temp = nums2[k] * nums2[j]
				if temp - math.ceil(temp ** 0.5) ** 2 == 0:
					cnt2[temp] += 1
		print(cnt1, cnt2)
		res = 0
		for t in nums1:
			res += cnt2[t ** 2]
		for t in nums2:
			res += cnt1[t ** 2]
		return res
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		num1_dict = collections.defaultdict(int)
		num2_dict = collections.defaultdict(int)
		for num in nums1:
			num1_dict[num] += 1
		for num in nums2:
			num2_dict[num] += 1
		res = 0
		for num in num1_dict:
			double = num ** 2
			for num2 in num2_dict:
				if double % num2 == 0 and double // num2 in num2_dict:
					if num2 == double // num2:
						res += num2_dict[num2] * (num2_dict[num2] - 1) * num1_dict[num]
					else:
						res += num2_dict[num2] * num2_dict[double // num2] * num1_dict[num]
		for num in num2_dict:
			double = num ** 2
			for num2 in num1_dict:
				if double % num2 == 0 and double // num2 in num1_dict:
					if num2 == double // num2:
						res += num1_dict[num2] * (num1_dict[num2] - 1) * num2_dict[num]
					else:
						res += num1_dict[num2] * num1_dict[double // num2] * num2_dict[num]
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def lowerbound(target, left, right, nums):
			while left < right:
				mid = left + (right - left) // 2
				if nums[mid] == target:
					right = mid
				elif nums[mid] < target:
					left = mid + 1
				else:
					right = mid
			return left

		def higherbound(target, left, right, nums):
			while left < right:
				mid = left + (right - left) // 2
				if nums[mid] == target:
					left = mid + 1
				elif nums[mid] < target:
					left = mid + 1
				else:
					right = mid
			return left

		def helper(n, nums, memo):
			if n in memo:
				return memo[n]
			result = 0
			for i in range(len(nums)):
				if n % nums[i] != 0:
					continue
				target = n // nums[i]
				lower = lowerbound(target, i + 1, len(nums), nums)
				higher = higherbound(target, i + 1, len(nums), nums)
				result += higher - lower
			memo[n] = result
			return result
		result = 0
		memo1 = {}
		for n in nums1:
			result += helper(n * n, nums2, memo1)
		memo2 = {}
		for n in nums2:
			result += helper(n * n, nums1, memo2)
		return result


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		da = Counter(nums1)
		db = Counter(nums2)
		cnt = 0
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				p = nums2[i] * nums2[j]
				if math.isqrt(p) ** 2 == p and math.isqrt(p) in da:
					cnt += da[int(math.sqrt(p))]
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				p = nums1[i] * nums1[j]
				if math.isqrt(p) ** 2 == p and math.isqrt(p) in db:
					cnt += db[int(math.sqrt(p))]
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(memo1, memo2) = (collections.Counter(), collections.Counter())
		for (a, b) in itertools.combinations(nums1, 2):
			temp = int(math.sqrt(a * b))
			if temp ** 2 == a * b:
				memo1[temp] += 1
		for (a, b) in itertools.combinations(nums2, 2):
			temp = int(math.sqrt(a * b))
			if temp ** 2 == a * b:
				memo2[temp] += 1
		return sum((memo2[num] for num in nums1)) + sum((memo1[num] for num in nums2))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		r = 0
		c = Counter()
		for i in nums1:
			if i in c:
				r += c[i]
			for j in nums2:
				c[j * j / i] += 1
		c = Counter()
		for i in nums2:
			if i in c:
				r += c[i]
			for j in nums1:
				c[j * j / i] += 1
		return r


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sq1 = defaultdict(list)
		pd1 = defaultdict(list)
		sq2 = defaultdict(list)
		pd2 = defaultdict(list)
		for i in range(0, len(nums1)):
			n1 = nums1[i]
			sq1[n1 * n1].append(i)
			for j in range(i + 1, len(nums1)):
				n2 = nums1[j]
				pd1[n1 * n2].append([i, j])
		for i in range(0, len(nums2)):
			n1 = nums2[i]
			sq2[n1 * n1].append(i)
			for j in range(i + 1, len(nums2)):
				n2 = nums2[j]
				pd2[n1 * n2].append([i, j])
		type1 = 0
		type2 = 0
		for sq in sq1:
			if sq in pd2:
				type1 += len(sq1[sq]) * len(pd2[sq])
		for sq in sq2:
			if sq in pd1:
				type2 += len(sq2[sq]) * len(pd1[sq])
		return type1 + type2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		n = len(nums1)
		m = len(nums2)
		sq1 = list(map(lambda x: x ** 2, nums1))
		sq2 = list(map(lambda x: x ** 2, nums2))
		d1 = dict()
		d2 = dict()
		for num1 in list(set(nums1)):
			d1[num1] = dict()
			for i in range(n):
				if nums1[i] == num1:
					if i == 0:
						d1[num1][i] = 1
					else:
						d1[num1][i] = d1[num1][i - 1] + 1
				elif i == 0:
					d1[num1][i] = 0
				else:
					d1[num1][i] = d1[num1][i - 1]
		for num2 in list(set(nums2)):
			d2[num2] = dict()
			for i in range(m):
				if nums2[i] == num2:
					if i == 0:
						d2[num2][i] = 1
					else:
						d2[num2][i] = d2[num2][i - 1] + 1
				elif i == 0:
					d2[num2][i] = 0
				else:
					d2[num2][i] = d2[num2][i - 1]
		for i in range(n):
			for j in range(m - 1):
				tmp = sq1[i] // nums2[j]
				if sq1[i] % nums2[j] == 0:
					if tmp not in d2:
						continue
					ans += d2[tmp][m - 1] - d2[tmp][j]
		for j in range(m):
			for i in range(n - 1):
				tmp = sq2[j] // nums1[i]
				if sq2[j] % nums1[i] == 0:
					if tmp not in d1:
						continue
					ans += d1[tmp][n - 1] - d1[tmp][i]
		return ans


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		for n in nums1:
			t = defaultdict(int)
			for m in nums2:
				if n * n % m == 0 and n * n // m in t:
					count += t[n * n // m]
				t[m] += 1
		for n in nums2:
			t = defaultdict(int)
			for m in nums1:
				if n * n % m == 0 and n * n // m in t:
					count += t[n * n // m]
				t[m] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.helper(nums1, nums2) + self.helper(nums2, nums1)

	def helper(self, arr1, arr2):
		res = 0
		for num in arr1:
			res += self.twoProduct(num * num, arr2)
		return res

	def twoProduct(self, target, arr):
		visited = {}
		res = 0
		for num in arr:
			if not num:
				continue
			if target % num == 0 and target // num in visited:
				res += visited[target // num]
			if num not in visited:
				visited[num] = 1
			else:
				visited[num] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		cnt1 = collections.Counter()
		for j in range(len(nums2)):
			for i in range(len(nums1)):
				s = nums1[i] ** 2
				if s % nums2[j] == 0 and s // nums2[j] in cnt1:
					res += cnt1[s // nums2[j]]
			cnt1[nums2[j]] += 1
		cnt2 = collections.Counter()
		for j in range(len(nums1)):
			for i in range(len(nums2)):
				s = nums2[i] ** 2
				if s % nums1[j] == 0 and s // nums1[j] in cnt2:
					res += cnt2[s // nums1[j]]
			cnt2[nums1[j]] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(alist, blist):
			res = 0
			for a in alist:
				bset = collections.Counter()
				a2 = a * a
				for b in blist:
					if a2 / b in bset:
						res += bset[a2 / b]
					bset[b] += 1
			return res
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		set1 = Counter(nums1)
		set2 = Counter(nums2)
		N1 = len(nums1)
		N2 = len(nums2)
		n1sq = [n * n for n in nums1]
		n2sq = [n * n for n in nums2]
		ntr = 0
		for i1 in range(N1):
			for i2 in range(N2):
				if n1sq[i1] % nums2[i2] == 0:
					if nums1[i1] != nums2[i2] and n1sq[i1] // nums2[i2] in set2:
						ntr += 0.5 * set2[n1sq[i1] // nums2[i2]]
					elif nums1[i1] == nums2[i2]:
						ntr += 0.5 * (set2[nums2[i2]] - 1)
				if n2sq[i2] % nums1[i1] == 0:
					if nums2[i2] != nums1[i1] and n2sq[i2] // nums1[i1] in set1:
						ntr += 0.5 * set1[n2sq[i2] // nums1[i1]]
					elif nums2[i2] == nums1[i1]:
						ntr += 0.5 * (set1[nums1[i1]] - 1)
		return round(ntr)


class Solution:

	def productPresent(self, numbers, required):
		result = 0
		count = collections.defaultdict(int)
		for number in numbers:
			count[number] += 1
		for number in numbers:
			if required % number != 0:
				continue
			keyRequired = required // number
			if keyRequired in count and count[keyRequired] > 0:
				if keyRequired == number:
					result += count[keyRequired] - 1
				else:
					result += count[keyRequired]
			count[number] -= 1
		return result

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		result = 0
		for i in nums1:
			required = i * i
			result += self.productPresent(nums2, required)
		for i in nums2:
			required = i * i
			result += self.productPresent(nums1, required)
		return result


class Solution:

	def count(self, nums1: List[int], nums2: List[int]) -> int:
		c = 0
		for n in nums1:
			sq = n ** 2
			counter = Counter()
			for k in nums2:
				if sq % k == 0:
					c += counter[sq // k]
				counter[k] += 1
		return c

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.count(nums1, nums2) + self.count(nums2, nums1)


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ret = 0
		h1 = defaultdict(int)
		h2 = defaultdict(int)
		for x in nums1:
			h1[x] += 1
		for x in nums2:
			h2[x] += 1
		for x in nums1:
			for y in nums2:
				if x * x / y != x * x // y:
					continue
				key = x * x // y
				if h2[key] > 0:
					if key == y:
						ret += h2[key] - 1
					else:
						ret += h2[key]
		for x in nums2:
			for y in nums1:
				if x * x / y != x * x // y:
					continue
				key = x * x // y
				if h1[key] > 0:
					if key == y:
						ret += h1[key] - 1
					else:
						ret += h1[key]
		return ret // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0

		def helper(l1, l2):
			nonlocal ans
			c = Counter(l2)
			for x in l1:
				num = x * x
				c2 = c.copy()
				for i in range(len(l2)):
					curr = l2[i]
					c2[curr] -= 1
					if num % curr == 0 and num // l2[i] in c2:
						ans += c2[num // l2[i]]
		helper(nums1, nums2)
		helper(nums2, nums1)
		return ans


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(jk1, jk2) = (defaultdict(set), defaultdict(set))
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				jk1[nums1[j] * nums1[k]].add((j, k))
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				jk2[nums2[j] * nums2[k]].add((j, k))
		res = 0
		for i in range(len(nums1)):
			res += len(jk2[nums1[i] ** 2])
		for i in range(len(nums2)):
			res += len(jk1[nums2[i] ** 2])
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def getRes(arr1, arr2):
			count = 0
			n = len(arr2)
			max2 = arr2[-1]
			for i in range(len(arr1)):
				if arr1[i] > max2:
					break
				target = arr1[i] ** 2
				seen = collections.defaultdict(int)
				for j in range(n):
					if target / arr2[j] in seen:
						count += seen[target / arr2[j]]
					seen[arr2[j]] += 1
			return count
		nums1.sort()
		nums2.sort()
		return getRes(nums1, nums2) + getRes(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ret = 0
		(m, n) = (len(nums1), len(nums2))
		(_map1, _map2) = (Counter(nums1), Counter(nums2))
		for i in range(m):
			nums2_map = {**_map2}
			for j in range(n):
				nums2_map[nums2[j]] -= 1
				target = nums1[i] * nums1[i] / nums2[j]
				if nums2_map.get(target, 0) > 0:
					ret += nums2_map.get(target, 0)
		for i in range(n):
			nums1_map = {**_map1}
			for j in range(m):
				nums1_map[nums1[j]] -= 1
				target = nums2[i] * nums2[i] / nums1[j]
				if nums1_map.get(target, 0) > 0:
					ret += nums1_map.get(target, 0)
		return ret


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		d = {}
		drev = {}
		for (i, x) in enumerate(nums2):
			if x in drev:
				drev[x].add(i)
			else:
				drev[x] = {i}
		for (idx1, x) in enumerate(nums1):
			i2 = x * x
			d = drev.copy()
			drev.clear()
			for (idx, j) in enumerate(nums2):
				d[j].remove(idx)
				if j in drev:
					drev[j].add(idx)
				else:
					drev[j] = {idx}
				if i2 % j == 0:
					k = i2 // j
					if k in d:
						ans += len(d[k])
		d = {}
		drev = {}
		for (i, x) in enumerate(nums1):
			if x in drev:
				drev[x].add(i)
			else:
				drev[x] = {i}
		for (idx1, x) in enumerate(nums2):
			i2 = x * x
			d = drev.copy()
			drev.clear()
			for (idx, j) in enumerate(nums1):
				d[j].remove(idx)
				if j in drev:
					drev[j].add(idx)
				else:
					drev[j] = {idx}
				if i2 % j == 0:
					k = i2 // j
					if k in d:
						ans += len(d[k])
		return ans


class Solution:

	def numTriplets(self, a: List[int], b: List[int]) -> int:
		map1 = {}
		map2 = {}
		for i in range(len(a)):
			for j in range(len(a)):
				if i != j:
					if a[i] * a[j] not in map1.keys():
						map1[a[i] * a[j]] = 0
					map1[a[i] * a[j]] += 1
		for i in range(len(b)):
			for j in range(len(b)):
				if i != j:
					if b[i] * b[j] not in map2.keys():
						map2[b[i] * b[j]] = 0
					map2[b[i] * b[j]] += 1
		count = 0
		for i in a:
			if i * i in map2.keys():
				count += map2[i * i]
		for i in b:
			if i * i in map1.keys():
				count += map1[i * i]
		return count // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = collections.Counter(nums1)
		d2 = collections.Counter(nums2)
		ans = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				p = nums1[i] * nums1[j]
				if int(math.sqrt(p)) ** 2 == p and int(math.sqrt(p)) in d2:
					ans += d2[int(math.sqrt(p))]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				p = nums2[i] * nums2[j]
				if int(math.sqrt(p)) ** 2 == p and int(math.sqrt(p)) in d1:
					ans += d1[int(math.sqrt(p))]
		return ans


class Solution:

	def numTriplets(self, A: List[int], B: List[int]) -> int:

		def find(X, Y):
			res = 0
			for x in X:
				have = collections.Counter(Y)
				for (i, y) in enumerate(Y):
					have[y] -= 1
					if x * x % y == 0:
						res += have[x * x // y]
			return res
		return find(A, B) + find(B, A)


class Solution:

	def all_products(self, int_list):
		res_list = []
		for (idx, i) in enumerate(int_list):
			for j in int_list[idx + 1:]:
				res_list.append(i * j)
		return res_list

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		squared_nums1 = [i ** 2 for i in nums1]
		squared_nums2 = [i ** 2 for i in nums2]
		products_nums1 = self.all_products(nums1)
		products_nums2 = self.all_products(nums2)
		for i in set(squared_nums2):
			c1 = squared_nums2.count(i)
			c2 = products_nums1.count(i)
			res += c1 * c2
		for j in set(squared_nums1):
			d1 = squared_nums1.count(j)
			d2 = products_nums2.count(j)
			res += d1 * d2
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1 = list(Counter(nums1).items())
		nums2 = list(Counter(nums2).items())

		def find(target, count1, arr):
			seen = Counter()
			ans = 0
			for (a, count2) in arr:
				if target % a == 0:
					if (b := (target // a)) != a:
						ans += count1 * count2 * seen[b]
					else:
						ans += count1 * math.comb(count2, 2)
				seen[a] += count2
			return ans
		return sum((find(a * a, c, nums2) for (a, c) in nums1)) + sum((find(a * a, c, nums1) for (a, c) in nums2))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		self.count = 0

		def computeCount(nums1, nums2):
			hashMap = {}
			for i in range(len(nums1)):
				checkNum = nums1[i] ** 2
				for j in range(len(nums2)):
					modulus = checkNum / nums2[j]
					if modulus in hashMap:
						self.count += hashMap[modulus]
					if nums2[j] in hashMap:
						hashMap[nums2[j]] += 1
					else:
						hashMap[nums2[j]] = 1
				hashMap.clear()
		computeCount(nums1, nums2)
		computeCount(nums2, nums1)
		return self.count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def twoProduct(target, nums) -> int:
			goal = defaultdict(list)
			tot = 0
			for i in range(len(nums)):
				if len(goal[nums[i]]) != 0:
					tot += len(goal[nums[i]])
				goal[target / nums[i]].append(i)
			return tot
		count = 0
		for n in nums1:
			count += twoProduct(n * n, nums2)
		for n in nums2:
			count += twoProduct(n * n, nums1)
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		one = [i ** 2 for i in nums1]
		two = [j ** 2 for j in nums2]
		self.cnt = 0
		d1 = collections.defaultdict(int)
		self.calculate(one, nums2)
		self.calculate(two, nums1)
		return self.cnt

	def calculate(self, square, nums):
		for i in range(len(square)):
			target = square[i]
			d = collections.defaultdict(list)
			for j in range(len(nums)):
				if target % nums[j] == 0 and int(target / nums[j]) in d:
					self.cnt += len(d[target / nums[j]])
				d[nums[j]].append(j)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(a, b):
			res = 0
			for num in a:
				tar = num ** 2
				cnt = collections.defaultdict(int)
				for x in b:
					res += cnt[tar / x]
					cnt[x] += 1
			return res
		return helper(nums1, nums2) + helper(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		if not nums1 or not nums2:
			return 0
		return self.helper(nums1, nums2) + self.helper(nums2, nums1)

	def helper(self, nums1, nums2):
		lookup = {}
		count = 0
		for num2 in nums2:
			for num1 in nums1:
				square = num1 ** 2
				mod = square % num2
				divide = square // num2
				if square >= num2 and mod == 0 and (divide in lookup):
					count += lookup[divide]
			if num2 not in lookup:
				lookup[num2] = 0
			lookup[num2] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		if not nums1 or not nums2:
			return 0
		res = 0
		newlist1 = collections.defaultdict(set)
		newlist2 = collections.defaultdict(set)
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				key = nums2[i] * nums2[j]
				newlist1[key].add((i, j))
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				key = nums1[i] * nums1[j]
				newlist2[key].add((i, j))
		for n in nums1:
			if n ** 2 in newlist1:
				res += len(newlist1[n ** 2])
		for n in nums2:
			if n ** 2 in newlist2:
				res += len(newlist2[n ** 2])
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		table1 = {}
		table2 = {}
		res = 0
		for n in nums1:
			square = n * n
			table = {}
			for (j, m) in enumerate(nums2):
				if square % m == 0:
					remainder = square // m
					if remainder in table:
						res += table[remainder]
				if m not in table:
					table[m] = 0
				table[m] += 1
		for n in nums2:
			square = n * n
			table = {}
			for (j, m) in enumerate(nums1):
				if square % m == 0:
					remainder = square // m
					if remainder in table:
						res += table[remainder]
				if m not in table:
					table[m] = 0
				table[m] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(nums1Counter, nums2Counter, result) = (Counter(nums1), Counter(nums2), 0)

		def isPerfectSquare(n):
			squareRoot = math.sqrt(n)
			return {'status': squareRoot - floor(squareRoot) == 0, 'value': int(floor(squareRoot))}
		for (num2j, num2k) in combinations(nums2, 2):
			perfectSquare = isPerfectSquare(num2j * num2k)
			if perfectSquare['status']:
				result += nums1Counter[perfectSquare['value']]
		for (num1j, num1k) in combinations(nums1, 2):
			perfectSquare = isPerfectSquare(num1j * num1k)
			if perfectSquare['status']:
				result += nums2Counter[perfectSquare['value']]
		return result


from itertools import combinations

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(sq1, sq2) = ([num ** 2 for num in nums1], [num ** 2 for num in nums2])
		(prod1, prod2) = ([combo[0] * combo[1] for combo in combinations(nums1, 2)], [combo[0] * combo[1] for combo in combinations(nums2, 2)])
		result = 0
		for sq in set(sq1):
			result += sq1.count(sq) * prod2.count(sq)
		for sq in set(sq2):
			result += sq2.count(sq) * prod1.count(sq)
		return result


from collections import defaultdict
from typing import List

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		h1 = {}
		h2 = {}
		for n in nums1:
			if n in h1:
				h1[n] += 1
			else:
				h1[n] = 1
		for n in nums2:
			if n in h2:
				h2[n] += 1
			else:
				h2[n] = 1
		count = 0
		for n in nums1:
			n2 = n * n
			for v in list(h2.keys()):
				(q, m) = divmod(n2, v)
				if m != 0 or q not in h2:
					continue
				l1 = h2[v]
				if v == q:
					if l1 > 1:
						count += l1 * (l1 - 1)
				else:
					l2 = h2[q]
					count += l1 * l2
		for n in nums2:
			n2 = n * n
			for v in list(h1.keys()):
				(q, m) = divmod(n2, v)
				if m != 0 or q not in h1:
					continue
				l1 = h1[v]
				if v == q:
					if l1 > 1:
						count += l1 * (l1 - 1)
				else:
					l2 = h1[q]
					count += l1 * l2
		return int(count / 2)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		result = 0
		for i in range(len(nums1)):
			dic = collections.defaultdict(int)
			for j in range(len(nums2)):
				target = nums1[i] ** 2 / nums2[j]
				if target in dic:
					result += dic[target]
				dic[nums2[j]] += 1
		for i in range(len(nums2)):
			dic = collections.defaultdict(int)
			for j in range(len(nums1)):
				target = nums2[i] ** 2 / nums1[j]
				if target in dic:
					result += dic[target]
				dic[nums1[j]] += 1
		return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		res += sum((self.get_target_products(n * n, nums2) for n in nums1))
		res += sum((self.get_target_products(n * n, nums1) for n in nums2))
		return res

	def get_target_products(self, target, nums):
		d = collections.Counter()
		res = 0
		for i in range(len(nums)):
			if target / nums[i] in d:
				res += d[target / nums[i]]
			d[nums[i]] += 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		for i in range(len(nums1)):
			target = nums1[i] ** 2
			temp = defaultdict(int)
			for j in range(len(nums2)):
				if target / nums2[j] in list(temp.keys()):
					count += temp[target / nums2[j]]
				temp[nums2[j]] += 1
		for i in range(len(nums2)):
			target = nums2[i] ** 2
			temp = defaultdict(int)
			for j in range(len(nums1)):
				if target / nums1[j] in list(temp.keys()):
					count += temp[target / nums1[j]]
				temp[nums1[j]] += 1
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		memo1 = collections.defaultdict(set)
		memo2 = collections.defaultdict(set)
		for i in range(len(nums1)):
			memo1[nums1[i]].add(i)
		for i in range(len(nums2)):
			memo2[nums2[i]].add(i)
		cnt = 0
		for i in range(len(nums1)):
			sq = nums1[i] * nums1[i]
			for j in range(len(nums2)):
				if nums2[j] > sq:
					break
				if sq % nums2[j] != 0:
					continue
				target = sq // nums2[j]
				if target in memo2:
					cnt += len(memo2[target])
					if j in memo2[target]:
						cnt -= 1
		for i in range(len(nums2)):
			sq = nums2[i] * nums2[i]
			for j in range(len(nums1)):
				if nums1[j] > sq:
					break
				if sq % nums1[j] != 0:
					continue
				target = sq // nums1[j]
				if target in memo1:
					cnt += len(memo1[target])
					if j in memo1[target]:
						cnt -= 1
		return cnt // 2


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		counter1 = Counter(nums1)
		counter2 = Counter(nums2)
		ret = 0
		for (k, v) in counter1.items():
			for i in range(1, k):
				if i in counter2 and k * k / i in counter2:
					ret += v * counter2[i] * counter2[k * k / i]
			if counter2[k] >= 2:
				ret += v * counter2[k] * (counter2[k] - 1) / 2
		for (k, v) in counter2.items():
			for i in range(1, k):
				if i in counter1 and k * k / i in counter1:
					ret += v * counter1[i] * counter1[k * k / i]
			if counter1[k] >= 2:
				ret += v * counter1[k] * (counter1[k] - 1) / 2
		return int(ret)


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_products = productCounts(nums1)
		nums2_products = productCounts(nums2)
		nums1_squares = squareCounts(nums1)
		nums2_squares = squareCounts(nums2)
		result = 0
		for (square, count) in nums1_squares.items():
			result += count * nums2_products[square]
		for (square, count) in nums2_squares.items():
			result += count * nums1_products[square]
		return result

def productCounts(arr):
	result = Counter()
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			result.update((arr[i] * arr[j],))
	return result

def squareCounts(arr):
	result = Counter()
	for num in arr:
		result.update((num ** 2,))
	return result


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_squared = [i ** 2 for i in nums1]
		nums2_squared = [i ** 2 for i in nums2]
		c1 = collections.Counter(nums1)
		c2 = collections.Counter(nums2)
		res = 0
		for n1 in nums1:
			for target in nums2_squared:
				if target / n1 in c1:
					res += c1[target / n1]
					if n1 ** 2 == target:
						res -= 1
		for n2 in nums2:
			for target in nums1_squared:
				if target / n2 in c2:
					res += c2[target / n2]
					if n2 ** 2 == target:
						res -= 1
		return res // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		from collections import Counter
		set1 = Counter(nums1)
		set2 = Counter(nums2)
		ret = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				temp = int(math.sqrt(nums1[i] * nums1[j]))
				if temp ** 2 == nums1[i] * nums1[j] and temp in set2:
					ret += set2[temp]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				temp = int(math.sqrt(nums2[i] * nums2[j]))
				if temp ** 2 == nums2[i] * nums2[j] and temp in set1:
					ret += set1[temp]
		return ret


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def solve(n1s, n2s):
			answer = 0
			for num1 in n1s:
				m = collections.defaultdict(int)
				for num2 in n2s:
					if num1 ** 2 % num2 == 0:
						answer += m[num1 ** 2 // num2]
					m[num2] += 1
			return answer
		return solve(nums1, nums2) + solve(nums2, nums1)


from typing import List
import bisect
from math import comb

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		res = 0
		nums1.sort()
		nums2.sort()
		res += self.find(nums1, nums2)
		res += self.find(nums2, nums1)
		return res

	def find(self, n1, n2):
		res = 0
		for n in n1:
			left = 0
			right = len(n2) - 1
			while left < right:
				if n2[left] * n2[right] == n ** 2:
					if n2[left] == n2[right]:
						res += comb(right - left + 1, 2)
						while left < right and n2[left] == n2[left + 1]:
							left += 1
						while left < right and n2[right] == n2[right - 1]:
							right -= 1
					else:
						nl = 1
						nr = 1
						while left < right and n2[left] == n2[left + 1]:
							nl += 1
							left += 1
						while left < right and n2[right] == n2[right - 1]:
							nr += 1
							right -= 1
						res += nl * nr
					left += 1
					right -= 1
				elif n2[left] * n2[right] < n ** 2:
					left += 1
				else:
					right -= 1
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(target, nums):
			ret = 0
			target = target * target
			d = {}
			s = set()
			for n in nums:
				if n in d:
					s.add((min(n, target // n), max(n, target // n)))
				if target % n == 0:
					if target // n in d:
						d[target // n] += 1
					else:
						d[target // n] = 1
			for (a, b) in s:
				if a == b:
					ret += d[a] * (d[a] - 1) // 2
				else:
					ret += d[a] * d[b]
			return ret
		ans = 0
		for n1 in nums1:
			ans += helper(n1, nums2)
		for n2 in nums2:
			ans += helper(n2, nums1)
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(d1, d2) = (dict(), dict())
		for (idx, n1) in enumerate(nums1):
			d1[idx] = dict()
			for elm in nums1[idx + 1:]:
				try:
					d1[idx][elm] += 1
				except KeyError:
					d1[idx][elm] = 1
		for (idx, n2) in enumerate(nums2):
			d2[idx] = dict()
			for elm in nums2[idx + 1:]:
				try:
					d2[idx][elm] += 1
				except KeyError:
					d2[idx][elm] = 1
		good = 0
		for n1 in nums1:
			for (idx, n2) in enumerate(nums2):
				try:
					good += d2[idx][n1 ** 2 / n2]
				except KeyError:
					pass
		for n2 in nums2:
			for (idx, n1) in enumerate(nums1):
				try:
					good += d1[idx][n2 ** 2 / n1]
				except KeyError:
					pass
		return good


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = len(nums1)
		n2 = len(nums2)
		nn1 = []
		nn2 = []
		for j in range(n2):
			for k in range(j + 1, n2):
				nn2.append(nums2[j] * nums2[k])
		for j in range(n1):
			for k in range(j + 1, n1):
				nn1.append(nums1[j] * nums1[k])
		cnt = 0
		nnn1 = set(nums1)
		nnn2 = set(nums2)
		for i in nnn1:
			cnt += nn2.count(i * i) * nums1.count(i)
		for i in nnn2:
			cnt += nn1.count(i * i) * nums2.count(i)
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(num, nums):
			m = {}
			cnt = 0
			for n in nums:
				if num % n == 0:
					if m.get(num / n) is not None:
						cnt += m[num / n]
				if m.get(n) is None:
					m[n] = 1
				else:
					m[n] += 1
			return cnt
		res = 0
		for num in nums1:
			res += count(num * num, nums2)
		for num in nums2:
			res += count(num * num, nums1)
		return res


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		dic1 = defaultdict(list)
		dic2 = defaultdict(list)
		for (idx, i) in enumerate(nums1):
			dic1[i].append(idx)
		for (idx, i) in enumerate(nums2):
			dic2[i].append(idx)
		count = 0
		for i in nums1:
			sq = i * i
			for j in set(nums2):
				ano = sq / j
				if ano != int(ano):
					continue
				ano = int(ano)
				if ano in dic2:
					inc = 0
					if ano == j:
						inc += int(len(dic2[ano]) * (len(dic2[ano]) - 1) / 2)
					else:
						inc += len(dic2[ano]) * len(dic2[j]) / 2
					count += inc
		for i in nums2:
			sq = i * i
			for j in set(nums1):
				ano = sq / j
				if ano != int(ano):
					continue
				ano = int(ano)
				if ano in dic1:
					inc = 0
					if ano == j:
						inc += int(len(dic1[ano]) * (len(dic1[ano]) - 1) / 2)
					else:
						inc += len(dic1[ano]) * len(dic1[j]) / 2
					count += inc
		return int(count)


import math

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def isSquare(n):
			return math.sqrt(n) == int(math.sqrt(n))
		from collections import Counter
		hash1 = Counter(nums1)
		print(hash1)
		out = 0
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				k = nums2[i] * nums2[j]
				if isSquare(k):
					if int(math.sqrt(k)) in hash1:
						out += hash1[int(math.sqrt(k))]
		print(out)
		hash2 = Counter(nums2)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				k = nums1[i] * nums1[j]
				if isSquare(k):
					if int(math.sqrt(k)) in hash2:
						out += hash2[int(math.sqrt(k))]
		print(out)
		return out


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		for i in range(len(nums1)):
			hashmap = collections.defaultdict(int)
			for j in range(len(nums2)):
				if nums1[i] * nums1[i] / nums2[j] in hashmap:
					ans += hashmap[nums1[i] * nums1[i] / nums2[j]]
				hashmap[nums2[j]] += 1
		for i in range(len(nums2)):
			hashmap = collections.defaultdict(int)
			for j in range(len(nums1)):
				if nums2[i] * nums2[i] / nums1[j] in hashmap:
					ans += hashmap[nums2[i] * nums2[i] / nums1[j]]
				hashmap[nums1[j]] += 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		ans = 0
		for n in nums1:
			d = {}
			for (i, m) in enumerate(nums2):
				if n ** 2 / m in d:
					ans += d[n ** 2 / m]
				if m in d:
					d[m] += 1
				else:
					d[m] = 1
		for n in nums2:
			d = {}
			for (i, m) in enumerate(nums1):
				if n ** 2 / m in d:
					ans += d[n ** 2 / m]
				if m in d:
					d[m] += 1
				else:
					d[m] = 1
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()

		def ok(n, sorted_lst):
			(i, j) = (0, len(sorted_lst) - 1)
			ret = 0
			while 0 <= i < j < len(sorted_lst):
				t = sorted_lst[i] * sorted_lst[j]
				if t > n:
					j -= 1
					while i < j < len(sorted_lst) - 1 and sorted_lst[j] == sorted_lst[j + 1]:
						j -= 1
				elif t < n:
					i += 1
					while 0 < i < j and sorted_lst[i] == sorted_lst[i - 1]:
						i += 1
				elif sorted_lst[i] == sorted_lst[j]:
					ret += (j - i + 1) * (j - i) // 2
					break
				else:
					(a, b) = (1, 1)
					i += 1
					while 0 < i < j and sorted_lst[i] == sorted_lst[i - 1]:
						i += 1
						a += 1
					j -= 1
					while i <= j < len(sorted_lst) - 1 and sorted_lst[j] == sorted_lst[j + 1]:
						j -= 1
						b += 1
					ret += a * b
			return ret
		(tot, cur) = (0, 0)
		for (i, v) in enumerate(nums1):
			if i == 0 or v != nums1[i - 1]:
				cur = ok(v * v, nums2)
			tot += cur
		for (i, v) in enumerate(nums2):
			if i == 0 or v != nums2[i - 1]:
				cur = ok(v * v, nums1)
			tot += cur
		return tot


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_cnt = collections.Counter(nums1)
		nums1_square_cnt = {x * x: nums1_cnt[x] for x in nums1_cnt}
		nums2_cnt = collections.Counter(nums2)
		nums2_square_cnt = {y * y: nums2_cnt[y] for y in nums2_cnt}

		def f(nums_a, cnt_a, cnt_b_squares):
			uniq_a_vals = list(cnt_a.keys())
			if len(uniq_a_vals) == 1:
				x = uniq_a_vals[0]
				if x * x in cnt_b_squares:
					return cnt_a[x] * (cnt_a[x] - 1) // 2 * cnt_b_squares[x * x]
			total = 0
			for i in range(len(nums_a)):
				for j in range(i + 1, len(nums_a)):
					(x, y) = (nums_a[i], nums_a[j])
					if x * y in cnt_b_squares:
						total += cnt_b_squares[x * y]
			return total
		return f(nums1, nums1_cnt, nums2_square_cnt) + f(nums2, nums2_cnt, nums1_square_cnt)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = collections.Counter(nums1)
		c2 = collections.Counter(nums2)
		res = 0
		for x in c1:
			for y in c2:
				if x == y:
					res += c1[x] * c2[y] * (c2[y] - 1) // 2
				elif x ** 2 % y == 0 and y < x ** 2 // y:
					res += c1[x] * c2[y] * c2[x ** 2 // y]
		(c1, c2) = (c2, c1)
		for x in c1:
			for y in c2:
				if x == y:
					res += c1[x] * c2[y] * (c2[y] - 1) // 2
				elif x ** 2 % y == 0 and y < x ** 2 // y:
					res += c1[x] * c2[y] * c2[x ** 2 // y]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def f(u, v):
			v = Counter((float(i) for i in v))
			for x in u:
				w = x * x
				for y in v:
					if y == x:
						n = v[y]
						yield (n * (n - 1))
						continue
					z = w / y
					if z in v:
						yield (v[y] * v[z])
		a = sum(f(nums1, nums2)) + sum(f(nums2, nums1))
		return a // 2


from functools import lru_cache
from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find(target, arr):
			seen = Counter()
			count = 0
			for a in arr:
				if target % a == 0:
					count += seen[target // a]
				seen[a] += 1
			return count

		@lru_cache(None)
		def twoProduct1(target):
			return find(target, nums1)

		@lru_cache(None)
		def twoProduct2(target):
			return find(target, nums2)
		return sum((twoProduct2(a * a) for a in nums1)) + sum((twoProduct1(a * a) for a in nums2))


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find(target, arr):
			seen = Counter()
			count = 0
			for a in arr:
				if target % a == 0:
					count += seen[target // a]
				seen[a] += 1
			return count

		def twoProduct(target, nums):
			if target in lut:
				return lut[target]
			lut[target] = find(target, nums)
			return lut[target]
		lut = Counter()
		ret1 = sum((twoProduct(a * a, nums2) for a in nums1))
		lut = Counter()
		ret2 = sum((twoProduct(a * a, nums1) for a in nums2))
		return ret1 + ret2


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count1 = Counter(nums1)
		count2 = Counter(nums2)
		return self.count_triplets(count1, count2) + self.count_triplets(count2, count1)

	def count_triplets(self, count1, count2):
		triplets = 0
		for (n1, c1) in count1.items():
			for (n2, c2) in count2.items():
				n3 = n1 ** 2 / n2
				c3 = count2[n3]
				if n2 == n3:
					triplets += c1 * c3 * (c3 - 1) / 2
				else:
					triplets += c1 * c2 * c3 / 2
		return int(triplets)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sq1 = Counter([n ** 2 for n in nums1])
		sq2 = Counter([n ** 2 for n in nums2])
		triplets = self.count_triplets(sq1, nums2)
		triplets += self.count_triplets(sq2, nums1)
		return triplets

	def count_triplets(self, sqs: List[int], nums: List[int]) -> int:
		pairs = defaultdict(int)
		triplets = 0
		for n in nums:
			if n in pairs:
				triplets += pairs[n]
			for k in sqs:
				pairs[k / n] += sqs[k]
		return triplets


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		num1Map = defaultdict(int)
		for (i, n) in enumerate(nums1):
			num1Map[n] += 1
		num2Map = defaultdict(int)
		for (i, n) in enumerate(nums2):
			num2Map[n] += 1

		def count(nums, numsMap):
			out = 0
			same = 0
			for n1 in nums:
				sq = n1 * n1
				for (n2, v) in list(numsMap.items()):
					if sq / n2 == sq // n2:
						k = numsMap.get(sq // n2)
						if sq // n2 == n2:
							if k > 1:
								same += math.factorial(k) // (math.factorial(k - 2) * math.factorial(2))
						elif k:
							out += k * v
			return same + out // 2
		out = 0
		out += count(nums1, num2Map)
		out += count(nums2, num1Map)
		return out


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def countTriplets(nums1, nums2):
			num2idx = defaultdict(list)
			for (i, n) in enumerate(nums2):
				num2idx[n].append(i)
			res = 0
			ct1 = Counter(nums1)
			for n in ct1:
				nsq = n ** 2
				for (i, n1) in enumerate(nums2):
					(n2, mod2) = divmod(nsq, n1)
					if mod2 == 0 and n2 in num2idx:
						res += len([x for x in num2idx[n2] if x > i]) * ct1[n]
			return res
		return countTriplets(nums1, nums2) + countTriplets(nums2, nums1)


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = Counter(nums1)
		c2 = Counter(nums2)
		ans = 0
		for x in nums1:
			sqr = x * x
			for y in c2.keys():
				if sqr % y == 0:
					z = sqr // y
					if y == z:
						ans += c2[y] * (c2[y] - 1)
					else:
						ans += c2[y] * c2.get(z, 0)
		for x in nums2:
			sqr = x * x
			for y in c1.keys():
				if sqr % y == 0:
					z = sqr // y
					if y == z:
						ans += c1[y] * (c1[y] - 1)
					else:
						ans += c1[y] * c1.get(z, 0)
		return ans // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1.sort()
		nums2.sort()
		count = self.counttrip(nums1, nums2)
		count += self.counttrip(nums2, nums1)
		return int(count)

	def counttrip(self, nums1, nums2):
		seen = defaultdict(int)
		count = 0
		for i in nums1:
			p = i * i
			if p in seen:
				count += seen[p]
				continue
			localcount = 0
			left = 0
			right = len(nums2) - 1
			while left < right:
				if nums2[left] > p:
					break
				if nums2[left] * nums2[right] == p:
					if nums2[left] == nums2[right]:
						n = right - left + 1
						localcount += n * (n - 1) / 2
						break
					localcount += 1
					nleft = left + 1
					while nums2[nleft] == nums2[nleft - 1] and nleft < right:
						nleft += 1
						localcount += 1
					right -= 1
					left = 0
				elif nums2[left] * nums2[right] > p:
					right -= 1
				elif nums2[left] * nums2[right] < p:
					left += 1
			count += localcount
			seen[p] = localcount
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def cal(arr1, arr2):
			countMap = {}
			m = defaultdict(list)
			count = 0
			for i in range(len(arr2)):
				m[arr2[i]].append(i)
			for e in arr1:
				if e in countMap:
					count += countMap[e]
					continue
				c = 0
				for i in range(len(arr2)):
					if not e * e % arr2[i]:
						d = e * e // arr2[i]
						c += sum([0] + [1 for idx in m[d] if idx != i])
				countMap[e] = c
				count += c
			return count // 2
		return cal(nums1, nums2) + cal(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def count(arr1, arr2):
			res = 0
			dic = collections.Counter(arr1)
			for a in dic:
				counter = collections.Counter()
				for b in arr2:
					c = a * a / b
					if c in counter:
						res += counter[c] * dic[a]
					counter[b] += 1
			return res
		res = count(nums1, nums2)
		res += count(nums2, nums1)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		lookup1 = dict()
		lookup2 = dict()
		for num1 in nums1:
			lookup1[num1] = lookup1.get(num1, 0) + 1
		for num2 in nums2:
			lookup2[num2] = lookup2.get(num2, 0) + 1
		mem = dict()
		ans = 0
		ans1 = 0
		ans2 = 0
		for idx1 in range(len(nums1)):
			num1 = nums1[idx1]
			if num1 in mem:
				ans1 += mem[num1][0]
				ans2 += mem[num1][1]
				continue
			lookup1[num1] -= 1
			ans1_tmp = 0
			ans2_tmp = 0
			for idx2 in range(len(nums2)):
				num2 = nums2[idx2]
				lookup2[num2] -= 1
				if lookup2.get(num1 ** 2 / num2, 0) > 0:
					ans1_tmp += lookup2[num1 ** 2 / num2]
				lookup2[num2] += 1
				if lookup1.get(num2 ** 2 / num1, 0) > 0:
					ans2_tmp += lookup1[num2 ** 2 / num1]
			mem[nums1[idx1]] = (ans1_tmp, ans2_tmp)
			ans1 += ans1_tmp
			ans2 += ans2_tmp
			lookup1[num1] += 1
		return ans1 // 2 + ans2 // 2


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def find(target, arr):
			seen = Counter()
			count = 0
			for a in arr:
				if target % a == 0:
					count += seen[target // a]
				seen[a] += 1
			return count

		@lru_cache(None)
		def twoProduct1(target):
			return find(target, nums1)

		@lru_cache(None)
		def twoProduct2(target):
			return find(target, nums2)
		return sum((twoProduct2(a * a) for a in nums1)) + sum((twoProduct1(a * a) for a in nums2))

	def numTriplets2(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = collections.defaultdict(int)
		d2 = collections.defaultdict(int)
		for i in nums1:
			d1[i * i] += 1
		for i in nums2:
			d2[i * i] += 1
		res = 0
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				p = nums1[i] * nums1[j]
				if p in d2:
					res += d2[p]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				p = nums2[i] * nums2[j]
				if p in d1:
					res += d1[p]
		return res

	def numTriplets3(self, A1: List[int], A2: List[int]) -> int:
		A1.sort()
		A2.sort()
		(C1, C2) = (collections.Counter(A1), collections.Counter(A2))
		res = 0
		(N1, N2) = (len(A1), len(A2))
		seen = set()
		for (i, x) in enumerate(A1):
			for (j, y1) in enumerate(A2):
				if x * x < y1:
					break
				y2 = x * x // y1
				if x * x % y1 == 0 and y2 in C2:
					c = C2[y2]
					if x == y1:
						res += comb(c, 2)
					else:
						res += c * C2[y1]
					seen |= {y1, y2}
					break
		seen = set()
		for x in A2:
			for y1 in A1:
				if x * x < y1:
					break
				y2 = x * x // y1
				if x * x % y1 == 0 and y2 in C1:
					c = C1[y2]
					if x == y1:
						res += comb(c, 2)
					else:
						res += c * C1[y1]
					seen |= {y1, y2}
					break
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		prod_nums1 = collections.Counter([v1 * v2 for (v1, v2) in itertools.combinations(nums1, 2)])
		prod_nums2 = collections.Counter([v1 * v2 for (v1, v2) in itertools.combinations(nums2, 2)])
		return sum([prod_nums2[n1 ** 2] for n1 in nums1]) + sum([prod_nums1[n2 ** 2] for n2 in nums2])


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		nums1.sort()
		nums2.sort()

		def search(array1, array2):
			result = 0
			hashtable = defaultdict(int)
			for i in array2:
				hashtable[i] += 1
			for a in array1:
				squared = a ** 2
				met = []
				for i in list(hashtable.keys()):
					if i not in met:
						if squared % i == 0:
							complement = squared // i
							if complement != i:
								result += hashtable[i] * hashtable[complement]
								met.append(complement)
							else:
								met.append(i)
								result += sum([j for j in range(hashtable[i])])
			return result
		count += search(nums1, nums2)
		count += search(nums2, nums1)
		return count


from collections import Counter
from itertools import combinations

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		c1 = Counter([x * y for (x, y) in combinations(nums1, 2)])
		c2 = Counter([x * y for (x, y) in combinations(nums2, 2)])
		return sum([c1[x * x] for x in nums2]) + sum([c2[x * x] for x in nums1])


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def helper(nums, lookup):
			res = 0
			for maxNum in nums:
				prod = maxNum * maxNum
				for n in lookup.keys():
					if n <= maxNum and (not prod % n):
						m = prod // n
						res += lookup[n] * (lookup[n] - 1) // 2 if m == n else lookup[m] * lookup[n]
			return res
		return helper(nums1, collections.Counter(nums2)) + helper(nums2, collections.Counter(nums1))

	def numTriplets1(self, nums1: List[int], nums2: List[int]) -> int:
		(lookup1, lookup2) = (collections.defaultdict(int), collections.defaultdict(int))
		for n in nums1:
			lookup1[n] += 1
		for n in nums2:
			lookup2[n] += 1
		res = 0
		for k in [0, 1]:
			nums = nums1 if not k else nums2
			lookup = lookup1 if k else lookup2
			for i in range(len(nums)):
				for j in range(i + 1, len(nums)):
					prod = nums[i] * nums[j]
					k = int(math.sqrt(prod))
					if k * k == prod and k in lookup:
						res += lookup[k]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		m1 = collections.defaultdict(lambda : 0)
		m2 = collections.defaultdict(lambda : 0)
		for i in range(len(nums1)):
			m1[nums1[i] ** 2] += 1
		for i in range(len(nums2)):
			m2[nums2[i] ** 2] += 1
		ans = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				ans += m2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				ans += m1[nums2[i] * nums2[j]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def prod_finder(num_list1, num_list2):
			prod_map = {}
			for n in num_list1:
				prod_map[n * n] = 0
			for n in num_list1:
				prod_map[n * n] += 1
			count = 0
			for i in range(0, len(num_list2)):
				for j in range(i + 1, len(num_list2)):
					p = num_list2[i] * num_list2[j]
					if p in prod_map:
						count += prod_map[p]
			return count
		return prod_finder(nums1, nums2) + prod_finder(nums2, nums1)


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		nums1_sq_dct = collections.defaultdict(int)
		nums2_sq_dct = collections.defaultdict(int)
		res = 0
		for x in nums1:
			nums1_sq_dct[x ** 2] += 1
		for y in nums2:
			nums2_sq_dct[y ** 2] += 1
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				res += nums2_sq_dct[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				res += nums1_sq_dct[nums2[i] * nums2[j]]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(d1, d2) = ({}, {})
		for v in nums1:
			d1[v * v] = d1.get(v * v, 0) + 1
		for v in nums2:
			d2[v * v] = d2.get(v * v, 0) + 1
		res = 0
		for (i, v) in enumerate(nums1):
			for j in range(i + 1, len(nums1)):
				res += d2.get(v * nums1[j], 0)
		for (i, v) in enumerate(nums2):
			for j in range(i + 1, len(nums2)):
				res += d1.get(v * nums2[j], 0)
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		seta = {}
		setb = {}
		for i in nums1:
			if i * i in seta:
				seta[i * i] += 1
			else:
				seta[i * i] = 1
		for i in nums2:
			if i * i in setb:
				setb[i * i] += 1
			else:
				setb[i * i] = 1
		ans = 0
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in setb:
					ans += setb[nums1[i] * nums1[j]]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in seta:
					ans += seta[nums2[i] * nums2[j]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d1 = defaultdict(int)
		d2 = defaultdict(int)
		ans = 0
		for i in nums1:
			d1[i * i] += 1
		for i in nums2:
			d2[i * i] += 1
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				ans += d2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				ans += d1[nums2[i] * nums2[j]]
		return ans


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		d1 = {}
		d2 = {}
		for i in nums1:
			if i ** 2 not in d1:
				d1[i ** 2] = 1
			else:
				d1[i ** 2] += 1
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				prod = nums2[j] * nums2[k]
				if prod in d1:
					count += d1[prod]
		for i in nums2:
			if i ** 2 not in d2:
				d2[i ** 2] = 1
			else:
				d2[i ** 2] += 1
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				prod = nums1[j] * nums1[k]
				if prod in d2:
					count += d2[prod]
		return count


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		count = 0
		d1 = defaultdict(int)
		d2 = defaultdict(int)
		for n in nums1:
			d1[n * n] += 1
		for n in nums2:
			d2[n * n] += 1
		count = 0
		for i in range(0, len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				count += d2[nums1[i] * nums1[j]]
		for i in range(0, len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				count += d1[nums2[i] * nums2[j]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sq1 = collections.Counter([nums1[i] * nums1[j] for i in range(len(nums1)) for j in range(i)])
		sq2 = collections.Counter([nums2[i] * nums2[j] for i in range(len(nums2)) for j in range(i)])
		return sum((sq1[n ** 2] for n in nums2)) + sum((sq2[n ** 2] for n in nums1))


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		sqr_nums1 = defaultdict(int)
		sqr_nums2 = defaultdict(int)
		res = 0
		for x in nums1:
			sqr_nums1[x * x] += 1
		for x in nums2:
			sqr_nums2[x * x] += 1
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				res += sqr_nums2[nums1[i] * nums1[j]]
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				res += sqr_nums1[nums2[i] * nums2[j]]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		hashmap1 = {}
		hashmap2 = {}
		count = 0
		for i in range(len(nums1)):
			if nums1[i] * nums1[i] not in hashmap1:
				hashmap1[nums1[i] * nums1[i]] = 1
			else:
				hashmap1[nums1[i] * nums1[i]] += 1
		for j in range(len(nums2)):
			if nums2[j] * nums2[j] not in hashmap2:
				hashmap2[nums2[j] * nums2[j]] = 1
			else:
				hashmap2[nums2[j] * nums2[j]] += 1
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				if nums1[i] * nums1[j] in hashmap2:
					count += hashmap2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				if nums2[i] * nums2[j] in hashmap1:
					count += hashmap1[nums2[i] * nums2[j]]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		prod1 = collections.defaultdict(int)
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				prod1[nums1[i] * nums1[j]] += 1
		prod2 = collections.defaultdict(int)
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				prod2[nums2[i] * nums2[j]] += 1
		count = 0
		for n in nums1:
			count += prod2[n * n]
		for n in nums2:
			count += prod1[n * n]
		return count


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(dic1, dic2) = (collections.defaultdict(int), collections.defaultdict(int))
		for num in nums1:
			dic1[num ** 2] += 1
		for num in nums2:
			dic2[num ** 2] += 1
		res = 0
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				res += dic2[nums1[i] * nums1[j]]
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				res += dic1[nums2[i] * nums2[j]]
		return res


import collections

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		if len(nums1) <= 1 and len(nums2) <= 1:
			return 0
		numTri = 0
		nums1Sq = [num ** 2 for num in nums1]
		nums2Sq = [num ** 2 for num in nums2]
		nums1Mul = collections.Counter([nums1[i] * nums1[j] for i in range(len(nums1)) for j in range(i + 1, len(nums1))])
		nums2Mul = collections.Counter([nums2[i] * nums2[j] for i in range(len(nums2)) for j in range(i + 1, len(nums2))])
		for num in nums1Sq:
			if num in nums2Mul:
				numTri += nums2Mul[num]
		for num in nums2Sq:
			if num in nums1Mul:
				numTri += nums1Mul[num]
		return numTri


from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		counter1 = Counter(nums1)
		counter2 = Counter(nums2)
		ret = 0
		for (k1, v1) in counter1.items():
			for (k2, v2) in counter2.items():
				if k1 * k1 / k2 in counter2:
					if k2 == k1:
						ret += v1 * v2 * (v2 - 1)
					else:
						ret += v1 * v2 * counter2[k1 * k1 / k2]
		for (k2, v2) in counter2.items():
			for (k1, v1) in counter1.items():
				if k2 * k2 / k1 in counter1:
					if k2 == k1:
						ret += v2 * v1 * (v1 - 1)
					else:
						ret += v1 * v2 * counter1[k2 * k2 / k1]
		return int(ret / 2)


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = len(nums1)
		n2 = len(nums2)
		n1_squares = defaultdict(int)
		n2_squares = defaultdict(int)
		for num1 in nums1:
			n1_squares[num1 * num1] += 1
			pass
		for num2 in nums2:
			n2_squares[num2 * num2] += 1
			pass
		triplets = 0
		for i in range(n1 - 1):
			for j in range(i + 1, n1):
				sq = nums1[i] * nums1[j]
				triplets += n2_squares[sq]
		for i in range(n2 - 1):
			for j in range(i + 1, n2):
				sq = nums2[i] * nums2[j]
				triplets += n1_squares[sq]
		return triplets


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		(cnt1, cnt2) = (defaultdict(int), defaultdict(int))
		for i in range(len(nums1)):
			for j in range(i + 1, len(nums1)):
				cnt1[nums1[i] * nums1[j]] += 1
		for i in range(len(nums2)):
			for j in range(i + 1, len(nums2)):
				cnt2[nums2[i] * nums2[j]] += 1
		ans = 0
		for i in nums1:
			ans += cnt2[i * i]
		for i in nums2:
			ans += cnt1[i * i]
		return ans


class Solution:

	def work(self, nums1, nums2):
		res = 0
		dic = {}
		for num in nums1:
			if num * num in dic:
				dic[num * num] += 1
			else:
				dic[num * num] = 1
		n = len(nums2)
		for i in range(n):
			for j in range(i + 1, n):
				if nums2[i] * nums2[j] in dic:
					res += dic[nums2[i] * nums2[j]]
		return res

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		return self.work(nums1, nums2) + self.work(nums2, nums1)


from typing import List
from collections import Counter

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		A = Counter([nums1[i] ** 2 for i in range(len(nums1))])
		B = Counter([nums2[i] ** 2 for i in range(len(nums2))])
		cnt = 0
		for j in range(len(nums2)):
			for k in range(j + 1, len(nums2)):
				cnt += A.get(nums2[j] * nums2[k], 0)
		for j in range(len(nums1)):
			for k in range(j + 1, len(nums1)):
				cnt += B.get(nums1[j] * nums1[k], 0)
		return cnt


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		d = {}
		ct = 0
		M = len(nums1)
		N = len(nums2)
		for i in range(M):
			if nums1[i] * nums1[i] in d:
				d[nums1[i] * nums1[i]] += 1
			else:
				d[nums1[i] * nums1[i]] = 1
		for i in range(N):
			for j in range(i + 1, N):
				if nums2[i] * nums2[j] in d:
					ct += d[nums2[i] * nums2[j]]
		d = {}
		for i in range(N):
			if nums2[i] * nums2[i] in d:
				d[nums2[i] * nums2[i]] += 1
			else:
				d[nums2[i] * nums2[i]] = 1
		for i in range(M):
			for j in range(i + 1, M):
				if nums1[i] * nums1[j] in d:
					ct += d[nums1[i] * nums1[j]]
		return ct


from collections import defaultdict

class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:

		def get_sq_cnt(nums):
			cnt = defaultdict(int)
			n = len(nums)
			for i in range(n):
				for j in range(i + 1, n):
					cnt[nums[i] * nums[j]] += 1
			return cnt
		(cnt1, cnt2) = (get_sq_cnt(nums1), get_sq_cnt(nums2))
		res = 0
		for num1 in nums1:
			res += cnt2[num1 * num1]
		for num2 in nums2:
			res += cnt1[num2 * num2]
		return res


class Solution:

	def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
		dict1 = Counter([x ** 2 for x in nums1])
		dict2 = Counter([x ** 2 for x in nums2])
		count = 0
		for i in range(len(nums2) - 1):
			for j in range(i + 1, len(nums2)):
				count += dict1[nums2[i] * nums2[j]]
		for i in range(len(nums1) - 1):
			for j in range(i + 1, len(nums1)):
				count += dict2[nums1[i] * nums1[j]]
		return count


class Solution:

	def numTriplets(self, f: List[int], s: List[int]) -> int:
		from collections import defaultdict

		def helper(nums1, nums2):
			d = defaultdict(int)
			ans = 0
			for i in range(len(nums1)):
				for j in range(i + 1, len(nums1)):
					d[nums1[i] * nums1[j]] += 1
			for num in nums2:
				ans += d[num ** 2]
			return ans
		return helper(f, s) + helper(s, f)