MOD = 998244353 def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 A = list(map(int, input[idx:idx + N])) # Precompute smallest prime factors up to 1e6 max_a = 10**6 spf = list(range(max_a + 1)) for i in range(2, int(max_a**0.5) + 1): if spf[i] == i: for j in range(i * i, max_a + 1, i): if spf[j] == j: spf[j] = i def factorize(x): factors = set() if x == 1: return factors while x != 1: p = spf[x] factors.add(p) while x % p == 0: x //= p return factors cnt = dict() answer = 0 for x in A: primes = factorize(x) if not primes: answer = (answer + 1) % MOD continue primes = list(primes) k = len(primes) sum_terms = 0 subsets = [] for mask in range(1, 1 << k): subset = [] for i in range(k): if mask & (1 << i): subset.append(primes[i]) subsets.append(subset) for subset in subsets: m = len(subset) d = 1 for p in subset: d *= p term = cnt.get(d, 0) if m % 2 == 1: sum_terms = (sum_terms + term) % MOD else: sum_terms = (sum_terms - term) % MOD new = (sum_terms + 1) % MOD answer = (answer + new) % MOD for subset in subsets: m = len(subset) d = 1 for p in subset: d *= p cnt[d] = (cnt.get(d, 0) + new) % MOD print(answer % MOD) if __name__ == '__main__': main()