רכב מחקר המבצע משימה בינלאומית על מאדים התקלקל. כדי להשיב אותו לפעולה יש להגדיל את הספק הסוללה שלו.

הספק הסוללה של הרכב מיוצג על ידי מספר שלם חיובי. ההספק הנוכחי הוא $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$.

תתי־משימות

הנקודות עבור כל תת־משימה מוענקות רק אם עוברים את כל הבדיקות של אותה תת־משימה ושל תתי־המשימות הנדרשות לה.