Today HNU is holding the hucpc2021, yuki is very excited and wants to attend this amazing contest. Unfortunately, the contest needs a team to participate, yuki can register a team only himself. However, yuki too weak and he does not want to compete with other teams only himself. Therefore poor yuki asks volunteers for help. After the volunteer's introduction, yuki knows two genius persons called emofunc and playf already registered a team, poor yuki finds them and tells them about his embarrassing situation. Emofunc and playf are generous and kind-hearted mans, they are so glad and decide to let yuki join their team. After 5 hours of exciting competition, there is no doubt that emofunc and playf win the champion in hucpc2021! Yuki is a really lucky dog because he  has done nothing in the whole competition, poor yuki is so curious why emofunc and playf so strong and asks them for some life experiences. Emofunc and playf are very generous mans so they tell yuki a lot. After that, yuki knows emofunc and playf not only are very genius and study hard but also are magicians.

Yuki has an apple and there are  participants in hucpc2021, he wants to share the apple to every participants, so he decides to divide the apple into  pieces. But yuki is shocked after he knows the magic power of emofunc and playf. Playf's magic power can copy an item into ten and emofunc's magic power can copy an item into what number he wants, but emofunc lies to yuki and he says his magic power only can copy an item into x (emofunc always pretend he so weak). Yuki knows both the magic power of emofunc and playf then he decides not to divide the apple and he wants to bother emofunc and playf.

Yuki has two choices and assumes he has  apple(s) now:

1. Bother playf. Give all the apples yuki has to playf, then playf uses his magic and returns apples to yuki, which is mean yuki has apples now.

2. Bother emofuc. Give an apple to emofuc, then emofunc uses his magic and returns apples to yuki, which is mean yuki has  apples now.

Yuki wants to minimize the total number of times of bother emofunc and playf, and let the total number of apples can be divided into  equal parts without split into pieces (image all apples are same), in other words, yuki has  apples now and can be divided by . It is so difficult to yuki and yuki wants your help, can you tell the minimum number of total times to bother emofunc and playf to yuki?