#include <bits/stdc++.h>
using namespace std;
#define max 100000
bool arr[100001];
int sp[100001];
void soe()
{
int i, j;
memset(arr, true, sizeof(arr));
arr[0] = false;
arr[1] = false;
for(i = 4; i <= max; i += 2)
arr[i] = false;
for(i = 3; i * i <= max; i += 2)
{
if(arr[i])
{
for(j = i * i; j <= max; j += i)
arr[j] = false;
}
}
}
void spf()
{
int i, j;
for(i = 2; i <= max; i += 2)
sp[i] = 2;
for(i = 3; i <= max; i += 2)
{
if(arr[i])
{
sp[i] = i;
for(j = i; j * i <= max; j += 2)
sp[j * i] = i;
}
}
}