Effektiv olun
Gəlin tam ədədlərdən ibarət bir ardıcıllığı nəzərdən keçirək. Bu ardıcıllıq n elementdən ibarətdir: x_0 = a,
x_i = ((x_i-1 * b + c) % m) + 1 burada i = 1, 2, ..., n - 1.
Verilmiş ədədlər a, b, c, m, n ilə, cəmi m-ə bölünən "ardıcıl altardıcıllıqların" sayını tapın.
Məsələn, a = 2, b = 1, c = 2, m = 4, n = 4 üçün:
x_0 = 2,
x_i = (x_i-1 + 2) % 4 + 1, i = 1, 2, 3, 4.
Bu halda x_0 = 2, x_1 = 1, x_2 = 4, x_3 = 3. Ardıcıl altardıcıllıqlar {2}, {2, 1}, {2, 1, 4}, {2, 1, 4, 3}, {1}, {1, 4}, {1, 4, 3}, {4}, {4, 3} və {3} olacaq. Bu 10 altardıcıllıqdan yalnız ikisinin cəmi 4-ə bölünür: {1, 4, 3} və {4}.
Giriş verilənləri
Birinci sətir testlərin sayını t (t < 500) ehtiva edir. Hər bir növbəti sətir ayrıca testdir və beş tam ədəd ehtiva edir: a, b, c, m, n (0 ≤ a, b, c ≤ 1000, 0 < m, n ≤ 10000).
Çıxış verilənləri
Hər bir test üçün ayrıca sətirdə onun nömrəsini və tələb olunan nəticəni çıxarın.