Medium Divide and Conquer > Dynamic Programming

**Sanvi** is a very cute girl. She likes to play Card game very much. One day, she came with some cards. In her Card game there may be maximum of **13** and there will be at least two Cards. Each card has a positive integer written on it . At the begin of game, Saanvi would like to make some shuffle of cards on her hand as much time as she likes so that the summation of absolute difference of every two consecutive cards from top to bottom on her hand will be maximum. Your task is to help her to find out in how many ways she can shuffle to get this maximum summation. Input: ------ Input starts with an integer **T (1 ≤ T ≤ 100)**, denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 13)** denoting the number of Cards in current game. The next line will contain N integers separated by spaces, **ith** of which denotes the value written on **Card number- i** . Each of these integers will be a **positive integer upto 10<sup>12</sup>**. Output: ------- For each case of input, output the number of ways of she can shuffle to get the maximum summation. Sample Input ------------ 3 2 1 5 3 1 3 5 3 8 8 8 Sample Output ------------- 2 4 6 For second Test case , 4 possible shuffle to get the maximum summation (which is 6) is [1,5,3] , [3,5,1] , [3,1,5] , [5,1,3]

Md. Tariqul Islam