void work(int n)
{
	int tot = 0;
	mu[1] = 1;vis[1] = 1;
	for(int i = 2;i <= n;i++)
	{
		if(!vis[i])
		{
			p[++tot] = i;mu[i] = -1;
		}
		for(int j = 1;j <= tot && i*p[j] <= n;j++)
		{
			vis[i*p[j]] = 1;
			if(i%p[j] == 0) 
			{
				mu[i*p[j]] = 0;
				break;
			}
			mu[i*p[j]] = -1LL*mu[i];
		}
	}
}