Ev tapşırığı
Vasya İqtisadiyyat Maarifi Təhsil Müəssisəsində (İMTM) təhsil alır və ona yeni bir ev tapşırığı verilib. Lakin onun belə şeylərə vaxtı yoxdur, çünki o, demək olar ki, NP-tam məsələsini polinomial vaxtda həll etməyə çox yaxındır, bu da bütün elmi ictimaiyyəti sarsıdacaq. Vasya maksimum axın məsələsini həll etməyə çox yaxınlaşıb! Gəlin Vasya-nı Edmonslar, Dinitslər və digərləri ilə narahat etməyək, sadəcə ona ev tapşırığını yerinə yetirməkdə kömək edək, çünki onun vaxtı məhduddur.
Tapşırıq m — müsbət tam ədəd və q tapşırıqlardan ibarətdir. i-ci tapşırığın şərti m ilə qarşılıqlı sadə olan tək bir tam ədəd x_i-dən ibarətdir. Tapşırığın cavabı elə minimal müsbət tam ədəddir ki, bu ədədin m-ə bölünməsindən qalan 1-ə bərabərdir. Əgər belə bir ədəd mövcud deyilsə, cavab -1-dir.
Giriş verilənləri
Birinci sətirdə boşluqla ayrılmış iki tam ədəd m və q (2 ≤ m ≤ 10^14, 1 ≤ q ≤ 2000) yazılıb. Növbəti q sətirdə i-ci tapşırığın şərti olan tək bir ədəd x_i (1 ≤ x_{i }< m, x_i m ilə qarşılıqlı sadədir) verilib.
Çıxış verilənləri
q tam ədəd çıxarın, hər biri ayrıca sətirdə. i-ci sətir i-ci tapşırığın cavabını ehtiva etməlidir.