Team TripleK là măng non đầy tiềm năng của câu lạc bộ H3.2PL, gồm các coder sắp lên năm hai. Trong các công việc, họ rất chỉnh chu, nghiêm túc đến mức ai cũng mắc phải hội chứng ám ảnh về sự hoàn hảo (OCPD). Một ngày trong lúc sinh ra mảng số nguyên để test thuật toán đơn giản, họ thấy rằng các số sinh ra được chưa đẹp lắm: Khôi đi tính tổng các chữ số của mỗi số và Khang đổi nó ra hệ nhị phân, Kiệt thì muốn rằng số đổi ra được chỉ chứa đúng một chữ số ~1~, team sẽ coi số như thế là số OCPD. Chẳng hạn ~2024~ là số OCPD vì ~2+0+2+4=8~ và trong hệ nhị phân thì ~8=1000~, chỉ chứa có một chữ số ~1~.

Họ muốn tất cả ~n~ số họ sinh ra ban đầu đều phải OCPD nên nếu số nào chưa có tính chất này thì họ sẽ tăng số đang có lên ~1~ đơn vị và cứ làm như thế đến khi nào gặp được số OCPD đầu tiên thì thôi. Hãy giúp team TripleK tính xem họ cần thực hiện tổng cộng bao nhiêu lần cho mảng hiện tại nhé.

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^5~, dòng tiếp theo gồm ~n~ số nguyên dương không vượt quá ~10^6.~

Output

Kết quả của bài toán.

Sample input

4
1 2 4 17

Sample output

0

Sample input

1
2023

Sample output

1

Giải thích: trong VD1, dễ thấy rằng khi tính tổng chữ số và đổi sang hệ nhị phân thì thu được: ~1,10,100,1000~, đều thoả mãn tiêu chí OCPD, vậy nên không cần làm gì cả. Còn trong VD2, số ~2023~ hiện tại chưa OCPD nhưng chỉ cần thêm ~1~ đơn vị nữa là được.