1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93

int sieve_size;
bitset<10000001> bs;
vector<int> pr;

void sieve(int size) {
	sieve_size = size;
	bs.set(); bs[0] = bs[1] = 0;
  	for (ll i = 2; i <= sieve_size; ++i) if (bs[i]) {
		for (ll j = i * i; j <= sieve_size; j += i) bs[j] = 0;
		pr.push_back(i);
	}
}

bool is_prime(ll N) {
	if (N <= sieve_size) return bs[N];
	for (int i = 0; i < pr.size() && pr[i] * pr[i] <= N; ++i) if (N % pr[i] == 0) return false;
  	return true;
}

vector<ii> factorize(ll N) {
	vector<ii> factors;
  	ll idx = 0, pf = pr[idx];
	while (N != 1 && pf * pf <= N) {
		if (N % pf == 0) {
			factors.emplace_back(pf, 0);
			while (N % pf == 0) { N /= pf; ++factors.back().s; }
		}
		pf = pr[++idx];	
  	}
	if (N != 1) factors.emplace_back(N, 1);
	return factors;
}

ll num_pf(ll N) {
	ll idx = 0, pf = pr[idx], ans = 0;
	while (N != 1 && pf * pf <= N) {
		while (N % pf == 0) { N /= pf; ans++; }
		pf = pr[++idx];
  	}
  	return ans + (N != 1);
}

ll num_diff_pf(ll N) {
  	ll idx = 0, pf = pr[idx], ans = 0;
  	while (N != 1 && pf * pf <= N) {
		if (N % pf == 0) ans++;
		while (N % pf == 0) N /= pf;
		pf = pr[++idx];
  	}
  	return ans + (N != 1);
}

ll sum_pf(ll N) {
	ll idx = 0, pf = pr[idx], ans = 0;
  	while (N != 1 && pf * pf <= N) {
		while (N % pf == 0) { N /= pf; ans += pf; }
		pf = pr[++idx];
  	}
  	return ans + (N != 1) * N;
}

ll num_div(ll N) {
	ll idx = 0, pf = pr[idx], ans = 1;
  	while (N != 1 && pf * pf <= N) {
		ll power = 0;
		while (N % pf == 0) { N /= pf; ++power; }
		ans *= (power + 1);
		pf = pr[++idx];
  	}
  	return (N != 1) ? 2 * ans : ans;
}

ll sum_div(ll N) {
  	ll idx = 0, pf = pr[idx], ans = 1;
  	while (N != 1 && pf * pf <= N) {
		ll power = 0;
		while (N % pf == 0) { N /= pf; ++power; }
		ans *= ((ll)pow((double)pf, power + 1.0) - 1) / (pf - 1);
		pf = pr[++idx];
  	}
  	if (N != 1) ans *= ((ll)pow((double)N, 2.0) - 1) / (N - 1);
  	return ans;
}

ll phi(ll N) {
	ll idx = 0, pf = pr[idx], ans = N;
	while (N != 1 && pf * pf <= N) {
		if (N % pf == 0) ans -= ans / pf;
		while (N % pf == 0) N /= pf;
		pf = pr[++idx];
	}
	return N != 1 ? ans - ans / N : ans;
}