Розглянемо цілочисельну послідовність, що складається з \textbf{n} елементів: \textbf{x_0} = \textbf{a}, \textbf{x_i} = ((\textbf{x_i}_\{-1\} * \textbf{b} + \textbf{c }) \% \textbf{m}) + \textbf{1} для \textbf{i} = \textbf{1}, \textbf{2}, ... \textbf{n} - \textbf{1} Задані числа \textbf{a}, \textbf{b}, \textbf{c}, \textbf{m}, \textbf{n}. Знайти кількість “послідовних підпослідовностей”, сума чисел яких ділиться на \textbf{m}. Розглянемо приклад, в якому \textbf{a }= \textbf{2}, \textbf{b} = \textbf{1}, \textbf{c} = \textbf{2}, \textbf{m} = \textbf{4}, \textbf{n} = \textbf{4}. Тоді \textbf{x_0} = \textbf{2}, \textbf{x_i} = (\textbf{x_i}_\{-1\} + \textbf{2}) \% \textbf{4} + \textbf{1}, \textbf{i = 1, 2, 3, 4} Звідки \textbf{x_0} = \textbf{2}, \textbf{x_1} = \textbf{1}, \textbf{x_2} = \textbf{4}, \textbf{x_3} = \textbf{3}. Послідовними підпослідовностями будуть \{\textbf{2}\}, \{\textbf{2 1}\}, \{\textbf{2 1 4}\}, \{\textbf{2 1 4 3}\}, \{\textbf{1}\}, \{\textbf{1 4}\}, \{\textbf{1 4 3}\}, \{\textbf{4}\}, \{\textbf{4 3}\} и \{\textbf{3}\}. Із перелічених \textbf{10} підпослідовностей сума лише двох ділиться на \textbf{4}: \{\textbf{1, 4, 3}\} та \{\textbf{4}\}. \InputFile Перший рядок містить кількість тестів \textbf{t} (\textbf{t} < \textbf{500}). Кожний наступний рядок є окремим тестом і містить п'ять цілих чисел: \textbf{a}, \textbf{b}, \textbf{c}, \textbf{m}, \textbf{n} (\textbf{0} ≤ \textbf{a}, \textbf{b}, \textbf{c} ≤ \textbf{1000}, \textbf{0} < \textbf{m}, \textbf{n} ≤ \textbf{10000}). \OutputFile Для кожного тесту в окремому рядку вивести його номер та потрібний результат.