import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) def hurui(n): """線形篩 pl: 素数のリスト mpf: iを割り切る最小の素因数 """ pl = [] mpf = [None]*(n+1) for d in range(2,n+1): if mpf[d] is None: mpf[d] = d pl.append(d) for p in pl: if p*d>n or p>mpf[d]: break mpf[p*d] = p return pl, mpf def factor(num): d = {} if num==1: return {1:1} while num>1: d.setdefault(mpf[num], 0) d[mpf[num]] += 1 num //= mpf[num] return d n = int(input()) pl, mpf = hurui(n) index = {} ps = [item for item in pl if item*item<=n] m = len(ps) for i,p in enumerate(ps): index[p] = i dp = [0]*(1<p: continue b0 = 0 for j in range(m): if v%ps[j]==0: b0 |= 1<