Sereja and Bubble Sort

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has an array A that contains n integers, namely A_{1}, A_{2}, ..., A_{n}. A single action consists of performing one of two following operations:
 To swap two consecutive elements;
 To make a random and uniform shuffle of all the elements of the array A.
Now Sereja's goal is to make the expected value of the function f(A) as minimal as possible, by doing no more than k actions.
The function f(A) is the minimal number of consecutive elements' swaps you need in order to sort the array A in the increasing order.
What is the expected value of f(A) in case Sereja uses no more than k actions in the optimal way?
Input
The first line contains an integer T, denoting the number of testcases. Then, T testcase descriptions follow.
The first line of each desription contains the integers n and k from the statement, respectively. The following line contains n space separated integers  A_{1}, A_{2}, ..., A_{n}. All the values of A_{i} will form a permutation of the first N natural numbers.
Output
For each test case output the minimal possible expected value of f(A). Your answer will be considered correct in case it differs by no more than 10^{6} from the official one.
Constraints
 1 ≤ T ≤ 100
 1 ≤ n ≤ 100
 0 ≤ k ≤ 10^{18}
 1 ≤ A_{i} ≤ n
Example
Input: 2 2 1 2 1 3 1 3 2 1 Output: 0.0000 1.5000
Author:  sereja 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/SEABUB 
Tags  dynamicprogramming, expectation, medium, sept14, sereja 
Date Added:  15032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 