Changlong'un qardaşı#3786
Changlong yaraşıqlı və ağıllı bir oğlandır və bir çox gözəl qızlar ona heyrandır. Hər gün o, həyat yoldaşı olmaq istəyən qızlardan on minlərlə məktub alır. Bu vəziyyətdən bezən Changlong bir gün bu narahatlıqdan qurtulmaq üçün bir fikir tapır. O, belə bir elan verir:
Yalnız aşağıdakı problemi həll edə bilən ağıllı qızlar onun həyat yoldaşı ola bilər.
Changlong-un problemi belədir:
a_1, a_2, \ldots, a_n rəqəmlərindən ibarət maraqlı bir ardıcıllıq var. Bu ardıcıllığın xüsusi bir xüsusiyyəti var: hər bir rəqəm dəqiq dəfə təkrarlanır, yalnız bir rəqəm istisna olmaqla, o isə dəfə təkrarlanır. Bu xüsusi rəqəmi ardıcıllıqdan necə çıxarmaq olar? Problemi daha maraqlı etmək üçün Changlong və rəqəmlərinin qarşılıqlı sadə olduğunu, yəni gcd(p, q) = 1 olduğunu fərz edir.
Changlong-un metodu çox yaxşı işləyir. Onun elanından sonra məktubların sayı xeyli azalıb. Qızlar bu problemi həll etməyə çalışırlar, lakin tezliklə bunun onların bacarıqlarını aşdığını başa düşürlər. Beləliklə, əksəriyyəti imtina edir, amma hələ də bu problemə davam gətirən bir qız var. Bir gün bu qız sizinlə qarşılaşır və sizdən ona kömək etməyinizi xahiş edir.
Girişin ilk sətrində (0 < k \leq 100) tam ədədi, yəni test hallarının sayı verilir.
Hər bir test halı üçün üç tam ədəd olan bir sətir olacaq: (0 < n \leq 10^7), , (1 < p, q < 200, gcd(p, q) = 1) və ardıcıllığın elementi a_i (0 < a_i < 10^7) olan bir sətir.
Hər bir test halı üçün əvvəlcə "Case #:" sətirini çıxarmalısınız, burada # test halının id nömrəsidir, sonra isə ardıcıllıqda dəfə təkrarlanan xüsusi rəqəm -ni çıxarmalısınız.
Nümunə 1