#include
#include
#include
#include
#include

using?namespace?std;

int?pr[10001];//素數集合
int?num[200000]?=?{0};
void?isprime（）//素數篩?
{
	int?n?=?200000;
	int?k?=?-1;
	for（int?i?=?2;?i?<=?n?;?i++）
	{
		if（num[i]?==?0）
		{
			pr[++k]?=?i;
			for（int?j?=?1;?j*i?<=?n;?j++）?
			{
				num[i*j]?=?1;
			}
		}
	?}?
	?if（k?==?10001）
	?{
	?	return;
	??}?
}?

int?gcd（int?aint?b）
//輾轉相除判斷互素?
{
????int?t;
????while（b）
	{
????????t=a;
????????a=b;
????????b=t%b;
????}
????return?a;
}
bool?husu（int?a?int?b）
{
	if（gcd（ab）?==?true）
	return?true;
	else
	return?false;
}


int?gete（int?rn）
{
	int?e?=?2;
	while（e<1?||?e>rn?||?!husu（ern））
	{
		e++;
	}
	return?e;
?}?
?int?getd（int?eint?rn）
?{
?	int?b?=?1;
?	while（?（?（e*b）?%?rn）?!=?1）
?	{
?		b++;
	?}
	?return?b;
?}
?int?rsa（int?aint?bint?c）
?{?
????int?t?=?ay?=?1;
????while（b!=0）
	{
????????y?*=?t;
????????y?%=?c;
????????b--;
????}