Iroha dan Kaguya baru-baru ini sangat tertarik pada sebuah permainan matematika berbasis bilangan bulat.

Pada awalnya, mereka berbagi sebuah bilangan bulat positif $n$. Kedua pemain bergantian melakukan operasi; satu ronde didefinisikan sebagai Iroha dan Kaguya masing-masing menyelesaikan satu operasi. Pada setiap ronde:

1. Iroha jalan pertama: Ia harus memilih sebuah bilangan bulat non-negatif $x$ ($0\le x<n$) dan mengganti nilai $n$ saat ini dengan $n+x$.

2. Kaguya jalan kedua: Ia harus memilih sebuah bilangan prima $p$ yang membagi $n$ saat ini (yaitu, $p\mid n$) dan mengganti nilai $n$ saat ini dengan $\frac{n}{p}$.

Operasi di atas berulang secara terus-menerus. Jika $n=1$ setelah akhir dari ronde mana pun, permainan langsung berakhir.

Selama permainan, Iroha bertujuan untuk memaksimalkan total jumlah ronde yang dimainkan, sedangkan Kaguya bertujuan untuk meminimalkan total jumlah ronde. Dengan asumsi kedua pemain sepenuhnya rasional dan menerapkan strategi optimal, tentukan total jumlah ronde yang pada akhirnya akan berlangsung dalam permainan tersebut.

Masukan

Baris pertama berisi sebuah bilangan bulat $n$ ($1\le n\le10^{18}$), yang menyatakan bilangan awal permainan.

Keluaran

Keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan total jumlah ronde permainan yang akan berlangsung jika kedua pemain bermain secara optimal.

Contoh

Masukan 1

1

Keluaran 1

0

Masukan 2

9

Keluaran 2

4

Masukan 3

16

Keluaran 3

5