АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Коронавирусийн улмаас олон газар хөл хорио тогтоож сургууль цэцэрлэгүүд орохоо больжээ.

Бусдын л адил гэрээсээ гаралгүй удсан ах дүү 2 уйдсан тул нэгэн тоглоом зохиож тоглохоор шийджээ.

Тэд гэртээ байгаа бүх хөзөрийг нийлүүлж тавиад ээлж ээлжээр хэдэн ширхэг хөзөр авсаар хэн нь

сүүлийн хөзөрийг авсан нь хожно.

Мэдээж хэрэг сонирхолтой дүрэм байхгүй бол уйтгартай тул дараах дүрмүүдийг зохиожээ:  

● Өөрийн ээлж дээрээ заавал хөзөр авах ёстой.

● Эхлэж авах хүн бүх хөзрийг авч болохгүй.

● Өмнөх хүний авсан хөзрийн тоо одоо авах хөзрийн тооны талаас илүүгүй байх.

● Хэрэв 1 хөзөр үлдсэн байвал дээрх дүрмүүд үйлчлэхгүй авч болно.  

Хэрэв тоглож байгаа ах дүүс байж болох хамгийн сайнаараа тоглосон бол хэн хожих вэ? 

Оролт 

Эхний мөрөнд тестийн тоо ​T (1 <= T <= 10)

Дараагийн T мөр тус бүрд нийт хөзрийн тоо ​N (1 <= N <= 10^​8 ​) ​өгөгдөнө.

Гаралт

Тест тус бүрт ялагчийг илтгэх 1 үг байна.

Эхлэсэн хүн ялсан бол “FIRST” үгүй бол “SECOND” гэж хэвлэнэ. 

Дэд бодлого

 1. Нийт тестний 20% N <= 100

2. Нийт тестний 50% ​N <= 10^​5

3. Нийт тестний 100% ​N <= 10^​8

Жишээ

Оролт

3

1

2

5 

Гаралт

FIRST

SECOND

SECOND 

Тайлбар

1 хөзөр байвал шууд хожно. 

2 хөзөр байхад эхлэсэн хүн 1-ийг авахаас өөр аргагүй 2 дахь хүн үлдсэн 1 хөзрийг авч хожно 

5 хөзөр байхад эхний хүн хамгийн багадаа 1 хамгийн ихдээ 4-н хөзөр авч болно. 

Хэрэв тэр 2, 3, эсвэл 4 хөзөр авбал 2 дахь хүн үлдсэн бүх хөзрийг авч шууд хожих тул 1 хөзөр авахаас өөр аргагүй. 

Эхний хүн 1-ийг авсны дараа 2 дахь хүн үлдсэн 4-н хөзөрнөөс хамгийн ихдээ 2-ийг авч болох боловч 2-ийг хожигдоно.

Иймд 2 дахь хүн мөн адил 1-ийг авна.  Эхний хүнд одоо 3н хөзөр үлдсэн гэвч ​өмнөх хүний авсан хөзрийн тоо 1 учраас

тэр ихдээ 2-ийг л авч чадна. ​Харин энэ удаад хэдийг ч авсан 2 дахь хүн ялалт байгуулна.