تعطلت مركبة تنفذ مهمة دولية على المريخ. ولاستعادة عملها، يجب زيادة قدرة بطاريتها.

تُمثل قدرة بطارية المركبة بعدد صحيح موجب. القدرة الحالية هي $a$، ولاستعادة عمل المركبة يجب زيادتها إلى $b$. يمكن إرسال إشارات خاصة من نوعين، X وY، من الأرض إلى المركبة لتغيير قدرة البطارية. تزيد إشارة من النوع X القدرة الحالية بمقدار $1$، وتزيد إشارة من النوع Y القدرة الحالية بمقدار $2$.

يريد منظمو المهمة الوصول إلى قدرة البطارية المطلوبة بإرسال أقل عدد ممكن من الإشارات. للأسف، بسبب تصميم المركبة، إذا أصبحت قدرة البطارية من مضاعفات العدد الصحيح $c$، تتعطل المركبة نهائيًا وتتوقف عن الاستجابة للإشارات.

اكتب برنامجًا يحدد، انطلاقًا من قدرة البطارية الابتدائية $a$ والقدرة المطلوبة $b$ والعدد الصحيح $c$، أقل عدد من الإشارات التي يجب إرسالها إلى المركبة لاستعادة عملها.

الإدخال

يحتوي الإدخال على ثلاثة أعداد صحيحة، $a$ و$b$ و$c$، كل منها في سطر منفصل ($1 \le a < b \le 10^9$، $2 \le c \le 10^9$، ولا $a$ ولا $b$ من مضاعفات $c$).

الإخراج

أخرج عددًا صحيحًا واحدًا: أقل عدد من الإشارات التي يجب إرسالها إلى المركبة.

أمثلة

الإدخال 1

2
7
3

الإخراج 1

3

الإدخال 2

4
10
3

الإخراج 2

4

ملاحظة

في المثال الأول، يمكن إرسال الإشارات Y ثم X ثم Y إلى المركبة. تتغير قدرة البطارية على النحو الآتي: $2 \to 4 \to 5 \to 7$.

في المثال الثاني، يمكن إرسال الإشارات X ثم Y ثم X ثم Y إلى المركبة. تتغير قدرة البطارية على النحو الآتي: $4 \to 5 \to 7 \to 8 \to 10$.

المهام الفرعية

تُمنح نقاط كل مهمة فرعية فقط إذا اجتازت جميع اختبارات تلك المهمة والمهام الفرعية المطلوبة لها.