#BT06. 第 K 张通行证

第 K 张通行证

第 K 张通行证

所有正整数编号中,与 NN 互质的编号按从小到大的顺序排列。

请输出这个序列中的第 KK 个数,序号从 11 开始。

例如,N=6N=6 时,这个序列以 1,5,7,11,13,17,…1,5,7,11,13,17,\ldots 开头。

输入格式

一行两个整数 N,KN,K。

输出格式

一行一个整数,表示第 KK 个与 NN 互质的正整数。

数据范围

1≤N,K≤1091\le N,K\le 10^9。

样例 1

6 5
13

样例 2

1 4
4