static void sieve(int max) {
		long[][] s = new long[max + 1][2];
		boolean[] v = new boolean[max + 1];
		int[] depth = new int[max + 1];
		for (int i = 0; i <= max; i++)
			s[i][0] = s[i][1] = 1;
		for (int i = 2; i <= max; i++)
			if (!v[i]) {
				s[i][0] = s[i][1] = 1;
				for (int j = i; j <= max; j += i) {
					s[j][0] *= (i - 1);
					s[j][1] *= i;
					v[j] = true;
				}
			}
		sum = new int[max + 1];
		depth[2] = 1;
		for (int i = 3; i <= max; i++)
			depth[i] = 1 + depth[(int) ((i * s[i][0]) / s[i][1])];
		for (int i = 2; i <= max; i++)
			sum[i] = sum[i - 1] + depth[i];
	}