You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

学姐听说大家在学排序，开开心心地把以前写的博客翻出来出题，但是学姐发现自己以前写的博客看不懂了，于是她点开了自己写的机器人，问它：“小U，为什么我看不懂我的归并排序博客了？”

小U回答她：“因为有人最近忙着阴阳师打超鬼王明日方舟刷活动原神新池子fgo过剧情phigros练手速云图计划新活动完了我喘不过气来了......”

学姐担忧地问它：“那怎么办，我这周还得出题呢？”

小U告诉她：“这样，我给你不超过k次交换相邻数字的机会，你在交换后的这组数里找出最少的逆序对有多少对，如果你找的出来，我就帮你出题。”

学姐想打游戏，没法静下心来写代码，你可以帮帮她吗？（ps：不能回答不可以）

善良的学姐担心有人不知道逆序对是啥，所以悄悄告诉你，给出一个序列a1、a2、…、an，逆序对是（i，j）的个数，其中1≤i<j≤n和ai>aj。

Input

T组输入

每一组第一行包含2个整数n，k（1≤N≤10^5,0≤K≤10^9)。

第二行包含n个整数a1，a2，…，an（0≤ai≤10^9)。

Output

每一组输出最小逆序对数。

Samples

1
3 0
2 2 1

2

2
3 1
2 2 1
5 2
4 4 2 3 8

1
2

Limitation

1s, 1024KiB for each test case.