Sirni

Ο μικρός Daniel έχει ένα σακουλάκι με ζαχαρωτά και ~N~ κάρτες.

Κάθε κάρτα έχει γραμμένο έναν θετικό ακέραιο αριθμό ~P_i~. Ενώ ο Daniel έτρωγε τα ζαχαρωτά του, σκέφτηκε ένα διασκεδαστικό παιχνίδι. Μπορεί να δέσει δύο κάρτες ~a~ και ~b~ και μετά αυτός πρέπει να φάει ~min(P_a~ % ~P_b,\;P_b~ % ~P_a)~ από τις καραμέλες, όπου η πράξη ~x~ % ~y~ δηλώνει το υπόλοιπο της διαίρεση του ~x~ με το ~y~.

Θέλει να δένει ζευγάρια χαρτιά με τρόπο που όταν σηκώνει ένα από αυτά, να σηκώνονται και όλα τα υπόλοιπα. Κάθε κάρτα μπορεί να συνδεθεί απευθείας με μια ένωση οποιουδήποτε αριθμού άλλων καρτών. Καθώς ο Daniel κοιτάζει τον εαυτό του, δεν θέλει να αναλωθεί πάρα πολύ, γι' αυτό σας ζητά να υπολογίσετε τον ελάχιστο αριθμό ζαχαρωτών που πρέπει να φάει, ώστε όλες οι κάρτες να είναι συνδεδεμένες.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(1 \le N \le 10^5)~.
Κάθε μία από τις ακόλουθες γραμμές ~N~ περιέχει έναν θετικό ακέραιο αριθμό ~P_i\;(1 \le P_i \le 10^5)~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει την απαιτούμενη τιμή που περιγράφηκε παραπάνω.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, θα ισχύει ~N \le 10^3~.
Σε δοκιμαστικές περιπτώσεις αξίας 40% των συνολικών πόντων, θα ισχύει ~P_i \le 10^6~.
Σε δοκιμαστικές περιπτώσεις αξίας 70% των συνολικών πόντων, ισχύει τουλάχιστον μία από τις δύο συνθήκες.

Παραδείγματα

input

4
2
6
3
11

output

1

Επεξήγηση του 1ου παραδείγματος:

Ο Daniel μπορεί να συνδέσει την πρώτη και τη δεύτερη κάρτα και να φάει 0 ζαχαρωτά, τη δεύτερη και την τρίτη και να φάει 0 ζαχαρωτά και την πρώτη και την τέταρτη και να φάει 1 ζαχαρωτό.

input

4
1
2
3
4

output

0

input

3
4
9
15

output

4