Стефан, еден од членовите на комисијата за натпревари, пред неколку дена добил повод за честење. Тој планира да ги почести членовите на комисијата со некое убаво чоколадо. Чоколадото кое што тој го купил е со правоаголен облик и е составено од R*C идентични коцки, соодветно распоредени во R редови и C колони.

Бидејќи Стефан одлично ги познава неговите колеги, тој знае дека на истите мора да им даде чоколадо кое што има точно N коцки, каде што N е бројот на сите останати членови на комисијата. Во спротивно, се ризикува да настане голема расправија околу поделбата на чоколадото - кој колку коцки да земе.

Ваша задача е да му помогнете на Стефан, кој е сега зафатен со планирање на претстојните животни настани, и да напишете програма која ќе пресмета со колку најмалку прекршувања тој може да добие "помало чоколадо" со точно N коцки. Доколку не е можно да се добие парче со точно N коцки, отпечатете -1. Во еден потег, чоколадото може да се скрши на два дела преку правење на точно едно хоризонтално или точно едно вертикално прекршување. На пример, чоколадо со димензии 3*2, може да се скрши на чоколади со димензии [2*2 и 1*2], [1*2 и 2*2] или [3*1 и 3*1] (види слика).

Влез

Во првата линија се запишани два цели броја R и C (1 <= R, C <= 2 000 000 000), кои го означуваат бројот на редови и колони од кои е составено чоколадото, соодветно.

Во втората линија е запишан еден цел број N (1 <= N <= 2 000 000 000), кој го означува бројот на членови на комисијата за натпревари (не сметајќи го Стефан).

Излез

Отпечатете го бараниот минимален број на прекршувања. (Или -1, доколку не е можно да се добијат точно N коцки).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 4
10

излез
1

влез
9 9
81

излез
0

влез
5 5
4

излез
2