Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.
 



Example 1:
Input: [4,6,15,35]
Output: 4



Example 2:
Input: [20,50,9,63]
Output: 2



Example 3:
Input: [2,3,6,7,4,12,21,39]
Output: 8


Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "'''\nIdea: 1. Prime factorize the given numbers\n      2. Map the factors to the indices in which they take part\n      3. Perform union operations on the list of indices belonging to same factor\n      4. Perform union operation to find the largest component\n\nTime complexity: O(n * sqrt(m)) where prime factorization 'sqrt(m)' is applied n times \nSpace complexity: O(n * log(m)) to keep all prime factors and maintain DSU\n'''\n\nimport collections, math\n\nclass DSU:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.sizeOf = [1] * n  \n    \n\n    def find(self, p):\n        # Find parent of given node\n        root = p\n        while self.parent[root] != root:\n            root = self.parent[root]\n\n        # Path compression\n        while p != root:\n            next_node = self.parent[root]    \n            self.parent[p] = root\n            p = next_node\n        \n        return root \n\n    \n    def union(self, x, y):\n        r1, r2 = self.find(x), self.find(y)\n\n        if r1 == r2:\n            return \n        if self.sizeOf[r1] > self.sizeOf[r2]:\n            self.sizeOf[r1] += self.sizeOf[r2]\n            self.parent[r2] = r1 \n        else:\n            self.sizeOf[r2] += self.sizeOf[r1]\n            self.parent[r1] = r2\n\n\nclass Solution:\n    def largestComponentSize(self, A):\n\n        def primeFactorization(n):\n            for i in range(2, int(math.sqrt(n))+1):\n                if n % i == 0:\n                    return primeFactorization(n//i) | set([i]) \n            return set([n])\n\n\n        n = len(A)\n        dsu = DSU(n)\n        primes = collections.defaultdict(list)\n\n        for i in range(n):\n            prime_factors = primeFactorization(A[i])\n            for factor in prime_factors:\n                primes[factor] += i, \n        \n        for factor in primes:\n            indices = primes[factor]\n            size = len(indices)\n            for i in range(size-1):\n                dsu.union(indices[i], indices[i+1]) \n        \n        components = collections.defaultdict(int)\n        \n        for index in range(n):\n            components[dsu.find(index)] += 1\n        \n        return max(components.values())\n\n        \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'largestComponentSize'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 8276