Let's consider some array A. The following algorithm calculates it's force:

1. Find all the continuous blocks where all the elemens of A are equal.
2. 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² + 3² + 1² + 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² + 3² + 1² + 3² = 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