Dırnaq, Kağız, Qayçı (Qızıl)

Siz, yəqin ki, «Daş, qayçı, kağız» oyunu haqqında eşitmisiniz. İnəklər buna bənzər bir oyun oynamağı sevirlər ki, onu «Dırnaq, kağız, qayçı» adlandırırlar.

«Dırnaq, kağız, qayçı» oyununun qaydaları sadədir. İki inək bir-birinə qarşı oynayır. Onlar üçə qədər sayır, bundan sonra eyni anda dırnağı, kağız vərəqini və ya qayçını bildirən jest göstərirlər. Dırnaq qayçını üstələyir (çünki dırnaq qayçını əzə bilər), qayçı kağızı üstələyir (çünki qayçı kağızı kəsə bilər), kağız isə dırnağı üstələyir (çünki dırnaq kağızla kəsilə bilər). Məsələn, əgər birinci inək «dırnaq», ikinci isə «kağız» göstərirsə, ikinci inək qalib gəlir. Əlbəttə ki, əgər hər iki inək eyni jesti göstərirsə, oyun heç-heçə ilə də bitə bilər.

Fermer Con öz ən yaxşı inəyi Bessi ilə «Dırnaq, kağız, qayçı» oyununun $n$ partiyasını oynamaq istəyir. Bessi bu oyunda ekspert olduğundan, FCon-un hər jestini o, göstərməzdən əvvəl proqnozlaşdıra bilir. Təəssüf ki, Bessi bir inək olduğundan, həm də çox tənbəldir. Buna görə də o, arxa-arxaya bir neçə dəfə eyni jesti göstərməyə meyllidir. Üstəlik, bütün partiyalar ərzində o, jestini ən çox $k$ dəfə dəyişməyə hazırdır. Məsələn, əgər k = 2 olarsa, o, ilk bir neçə partiyada «dırnaq» göstərə bilər, sonra bir müddət «kağız»a keçə bilər, daha sonra isə qalan partiyalarda yenidən «dırnaq»a keçə bilər.

FCon-un göstərəcəyi jestlərin verilmiş ardıcıllığına əsasən, Bessinin qazana biləcəyi maksimum partiya sayını müəyyən edin.