Sehr olunmuş musiqi qutuları

Lira, səyahətçi bard, Usta Melodiusdan, tanınmış sehrli sənətkardan, sehr olunmuş musiqi qutuları ilə dolu böyük bir yeşik aldı. Yeşiyi açanda onlarla gözəl bəzənmiş qutu bir məktubla birlikdə töküldü:

Hörmətli Lira,

Ümid edərəm ki, bu sehr olunmuş musiqi qutuları sənin çıxışlarına şadlıq gətirir. Qarışıqlığa görə üzür istəyirəm — sənin yola düşməzdən əvvəl onları düzgün təşkil etməyə vaxtım çatmadı. Hər qutu məkan sehri ilə gücləndirilmişdir: görəcəksən ki, kiçik qutular daha böyük qutuların içərisinə yerləşdirilə bilər, orada mükəmməl uyğunlaşır və ahəng içərisində melodiyalarını çalmağa davam edərlər.

Mahnıların ölkəni ovsunlasmın,

Usta Melodius

Liranın səyahət arabası artıq musiqi alətləri və sehrli artefaktlarla daşır. Qıymətli yerləri qorumaq üçün o, musiqi qutularını optimal şəkildə iç içə yerləşdirərək saxlamalı olduğu ən xarici qutuların sayını minimuma endirməyə qərar verir.

Hər sehr olunmuş musiqi qutusu unikal ölçüyə malikdir, s_i rəqəmi ilə təmsil olunur. i qutusu yalnız s_i < s_j olduqda j qutusunun içərisinə yerləşə bilər. Məkan sehrlərinin təbiətinə görə hər qutu birbaşa içərisində ən çox bir başqa qutu saxlaya bilər (bəzən də daxili qutu özü başqa bir qutu saxlaya bilər, iç içə zəncir yaradır).

Lira sehr olunmuş musiqi qutuları kolleksiyasmı təşkil edərkən, ona arabası üçün lazım olan ən xarici qutuların minimum sayını müəyyən etməyə kömək edə bilərsinizmi?

Giriş verilənləri

Giriş bir neçə test haldan ibarətdir. Hər test halı sehr olunmuş musiqi qutularının sayını göstərən tam ədəd N (1 ≤ N ≤ 10^5) ehtiva edən sətirlə başlayır. Bundan sonra N sətir gəlir, hər biri i-ci musiqi qutusunun ölçüsünü göstərən bir tam ədəd s_i (1 ≤ s_i ≤ 10^9) ehtiva edir. Giriş N = 0 olan sətirlə bitir, bu işlənməməlidir.

Çıxış verilənləri

Hər test halı üçün verilmiş sehr olunmuş musiqi qutularını optimal şəkildə iç içə yerləşdirərək əldə edilə bilən ən xarici qutuların minimum sayını təmsil edən tam ədəd ehtiva edən bir sətir çap edin.