import sys readline = sys.stdin.readline def divi(n): res = [] for i in range(1, int(n**0.5)+1): if n % i == 0: res.append(i) if i != n // i: res.append(n//i) return res from collections import Counter def prsh(N): prime = [2] for L in range(3,N): for p in prime: if not L % p: break if p > L**(1/2): prime.append(L) break return prime def popcount(i): assert 0 <= i < 0x100000000 i = i - ((i >> 1) & 0x55555555) i = (i & 0x33333333) + ((i >> 2) & 0x33333333) return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24 primes = prsh(10**5) def munum(N, C = Counter()): diviprimes = [] cnt = 0 p = 0 while N >= p**2: p = primes[cnt] if N % p == 0: diviprimes.append(p) N //= p while N % p == 0: N //= p cnt += 1 if N != 1: diviprimes.append(N) M = len(diviprimes) for i in range(1<