题目描述

如果两个正整数的最大公约数$（GCD）$为$1$，则称它们互质。例如，$1, 3, 5, 7, 9...$都与$2006$互质。

现在你的任务很简单：对于给定的整数$m$，找出这些按升序排列的互质元素中的第$K$个。

输入

输入包含多个测试用例。每个测试用例包含两个整数$m$（$1 \leq m \leq 1000000$）和$K$（$1 \leq K \leq 100000000$）。

输出

输出第$K$个互质元素，单独占一行。

样例输入

2006 1  
2006 2  
2006 3  

样例输出

1  
3  
5  

来源

POJ Monthly--2006.03.26, static