Alice and Bob are playing a simple game. They line up a row of n identical coins, all with the heads facing down onto the table and the tails upward.

For exactly mm times they select any k of the coins and toss them into the air, replacing each of them either heads-up or heads-down with the same possibility. Their purpose is to gain as many coins heads-up as they can.

Input

The input has several test cases and the first line contains the integer t(1≤t≤1000) which is the total number of cases.

For each case, a line contains three space-separated integers n, m1≤n,m≤100) and k (1≤k≤n).

Output

For each test case, output the expected number of coins heads-up which you could have at the end under the optimal strategy, as a real number with the precision of 33 digits.

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <cmath>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 typedef long long ll;

 int t,n,m,k;

 const int N=;

 double dp[N][N];

 double    c[N][N];//ll也会爆,一定要写成double

 double p[N];

 double ans;

 void C()

 {

     c[][]=;

     for(int i=;i<=;i++)

     {

         for(int j=;j<=i;j++)

         {

             if(j==||j==i) c[i][j]=;

             else {

                 c[i][j]=c[i-][j-]+c[i-][j];

             }

         }

     }

     p[]=;

     for(int i=;i<=;i++) p[i]=p[i-]/;

 }

 int main()

 {

     scanf("%d",&t);

     C();

     /*

     for(int i=1;i<=100;i++)

     {   printf("%dllll\n",i);

         for(int j=0;j<=i;j++)

         {

             printf("%d%c",c[i][j],j==i?'\n':' ');

         }

         //c[33][j]就爆int 了。

     }

     */

     while(t--)

     {

         scanf("%d%d%d",&n,&m,&k);

         memset(dp,,sizeof(dp));

         //dp[i][j]: i次操作后，正面朝上的面数为j的概率

         dp[][]=;//初始都是反面

         for(int i=;i<m;i++)

         {

             for(int j=;j<=n;j++)

             {

                for(int l=;l<=k;l++)//取得k个里面l个正面朝上。

                {   //反面的个数大于k，直接从反面的里面取k个

                    if((n-j)>=k)  dp[i+][j+l]+=dp[i][j]*c[k][l]*p[k];//取出的K个硬币每个的结果概率都是1/2（正/反）

                    //反面的个数小于k，只能再从已经是正面的里面再取出k-(n-j)个。

                    else  dp[i+][j-(k-(n-j))+l]+=dp[i][j]*c[k][l]*p[k];

                }

             }

         }

         ans=;

         for(int i=;i<=n;i++)ans+=i*dp[m][i];//期望,别忘了*i

         printf("%.3f\n",ans);

     }

     return  ;

 }