Function to precompute shortest prime factors
void sieve ( ) { memset ( spf , -1 , 100005 ) ; for ( int i = 2 ; i * i <= 100005 ; i ++ ) { for ( int j = i ; j <= 100005 ; j += i ) { if ( spf [ j ] == -1 ) { spf [ j ] = i ; } } } }