题目描述
Let's consider some array A. The following algorithm calculates it's force:
Find all the continuous blocks where all the elemens of A are equal.
Calculate sum of squared lengths of these blocks.
For example if array A = {2, 3, 3, 1, 1, 1, 4, 2, 2} its force will be 1^2 + 2^2 + 3^2 + 1^2 + 2^2 = 19
We can reorder some elements and get array with greater force. In the example above we can move the first element of A to the end and get array A = {3, 3, 1, 1, 1, 4, 2, 2, 2} with force 2^2 + 3^2 + 1^2 + 3^2 = 23.
You are given an array. What is the maximum force you can get by reordering some of its elements?
Input
The first line contains integer T denoting the number of test cases.
The following T lines contain 4 integers each: A[0], A[1], N, MOD.
Array A of N elements is generated by the following way:
A[0], A[1] are given
A[i] = (A[i - 1] + A[i - 2]) modulo MOD for 1 < i < N.
Output
For each test case output one integer on the separate line - answer for the question.
Constraints
1 ≤ T ≤100
0 ≤ A[0], A[1] ≤ 10^6
2 ≤ N ≤ 10^6
max(A[0] , A[1]) < MOD < 10^6
SAMPLE INPUT
2
0 1 6 4
1 1 4 2
SAMPLE OUTPUT
12
10
Explanation
Test case 1: array A = {0, 1, 1, 2, 3, 1}. The greatest possible force will be with the reordering {2, 0, 1, 1, 1, 3}
Test case 2: array A = {1, 1, 0, 1}. The greatest possible force will be with the reordering {1, 1, 1, 0}
输入格式
见题面
输出格式
见题面