Description

If you like playing overwatch,you must know the map Hanamura. This is the Genji and the Hanzo’s hometown.If you come to Hanamura,you can see many crane machines. Many players always destroy the creane machines before game start .So do you.But one day , there comes the leader of Hanamura.Her name is Haroro. Haroro is angry about what you have done. She wants to punish you .But She gives you a change. Now your job is easy: for the given integer m, find the $K$-th element which is relatively prime to m when these elements are sorted in ascending order. If you can’t solve problem,you will be suspended banned from overwatch forever.

Format

Input

The input contains multiple test cases. For each test case, it contains two integers $m (1 \leq m \leq 1000000), K (1 \leq K \leq 100000000)$.

Output

Output the answer in a single line.

Samples

1000 1
1000 2
1000 3
1000 4

1
3
7
9