Consider an integer sequence consisting of \textbf{n} elements, where \textbf{x_0} = \textbf{a}, \textbf{x_i} = ((\textbf{x_i}_\{-1\} * \textbf{b} + \textbf{c }) \% \textbf{m}) + \textbf{1} for \textbf{i} = \textbf{1} to \textbf{n} - \textbf{1} You will be given the values of \textbf{a}, \textbf{b}, \textbf{c}, \textbf{m} and \textbf{n}. Find out the number of consecutive subsequences whose sum is a multiple of \textbf{m}. Consider an example where \textbf{a} = \textbf{2}, \textbf{b} = \textbf{1}, \textbf{c} = \textbf{2}, \textbf{m} = \textbf{4} and \textbf{n} = \textbf{4}. Then \textbf{x_0} = \textbf{2}, \textbf{x_i} = (\textbf{x_i}_\{-1\} + \textbf{2}) \% \textbf{4} + \textbf{1}, \textbf{i = 1, 2, 3, 4} So, \textbf{x_0} = \textbf{2}, \textbf{x_1} = \textbf{1}, \textbf{x_2} = \textbf{4} and \textbf{x_3} = \textbf{3}. The consecutive subsequences are \{\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}\} and \{\textbf{3}\}. Of these \textbf{10} consecutive subsequences, only two of them adds up to a figure that is a multiple of \textbf{4}: \{\textbf{1 4 3}\} and \{\textbf{4}\}. \InputFile The first line of input is an integer \textbf{t} (\textbf{t} < \textbf{500}) that indicates the number of test cases. Eact case consists of \textbf{5} integers \textbf{a}, \textbf{b}, \textbf{c}, \textbf{m} and \textbf{n}. \textbf{a}, \textbf{b} and \textbf{c} will be non-negative integers not greater than \textbf{1000}. \textbf{n} and \textbf{m} will be a positive integers not greater than \textbf{10000}. \OutputFile For each test case, output the case number followed by the result.