//-------------------------------------------------------------------------------------------------------------------------------

//g++  7.4.0 

//Base File           

//-------------------------------------------------------------------------------------------------------------------------------

/*                                                 ᕙ(  • ‿ •  )ᕗ Dire Wolf

                                                     ->Manan's Code Pad<-

Patience                                                                                                                  Bravery

*/

//-------------------------------------------------------------------------------------------------------------------------------

//                                                     ¯\_(ツ)_/¯ <Code>

//-------------------------------------------------------------------------------------------------------------------------------

​

​

#include <bits/stdc++.h>

#define ll long long

#define PB push_back

#define F first

#define S second

​

​

using namespace std;

​

//Sieve-- If num is prime returns 0 else return one of its prime factor

vector<ll>prime(100000,0);

prime[0]=1;

prime[1]=1;

for(ll i=2; i*i<=100000; i++)

{

    if(prime[i])continue;

    for(ll j=2*i; j<=100000; j+=i)

        prime[j]=i;

}

​

//gcd-- Gives gcd of 2 numbers a and b