Рассмотрим целочисленную последовательность, состоящую из n элементов:

x0 = a,

xi = ((xi-1 * b + c) % m) + 1 для i = 1, 2, ... n - 1

Заданы числа a, b, c, m, n. Найти количество "последовательных подпоследовательностей", сумма чисел которых делится на m.

Рассмотрим пример, в котором a = 2, b = 1, c = 2, m = 4, n = 4. Тогда

x0 = 2,

xi = (xi-1 + 2) % 4 + 1, i = 1, 2, 3, 4

Откуда x0 = 2, x1 = 1, x2 = 4, x3 = 3. Последовательными подпоследовательностями будут {2}, {**2 1**}, {**2 1 4**}, {**2 1 4 3**}, {1}, {**1 4**}, {**1 4 3**}, {4}, {**4 3**} и {3}. Из перечисленных 10 подпоследовательностей сумма только двух делится на 4: {1, 4, 3} и {4}.

Входные данные

Первая строка содержит количество тестов t (t < 500). Каждая следующая строка является отдельным тестом и содержит пять целых чисел: a, b, c, m, n (0 ≤ a, b, c ≤ 1000, 0 < m, n ≤ 10000).

Выходные данные

Для каждого теста в отдельной строке вывести его номер и требуемый результат.