사랑의 흉터

이 문제는 굵게 표시한 $M$의 범위를 제외하면 사랑의 상처와 동일한 문제입니다.

저택의 꽃밭에는 셰리가 좋아하는 $N$가지 색깔의 장미가 자라고 있습니다. 각 색깔의 장미는 아주 많이 피어 있어서 꽃다발을 만들기에 부족할 일이 없답니다. 셰리는 장미를 몇 송이 따서 리본으로 묶어 소중한 친구를 위한 꽃다발을 만들어 보려고 해요.

다만 너무 많은 장미를 사용하면 셰리에게 꽃다발이 너무 무거워지기 때문에 사용된 장미의 개수는 $M$송이 이하여야 해요. 또한 같은 색의 장미 두 송이가 함께 꽃다발에 들어가면 꽃다발에 상처를 하나 남깁니다. 즉, 꽃다발에서 서로 다른 두 장미를 순서 없이 골랐을 때 두 장미의 색이 같은 경우의 수 만큼 상처가 생깁니다. 상처가 너무 많으면 꽃다발이 시들어 버리기 때문에 상처의 개수는 $K$개 이하여야 합니다.

셰리는 사랑을 한껏 담은 커다란 꽃다발을 만들고 싶습니다. 꽃다발을 구성할 수 있는 장미의 최대 개수를 구해주세요.

입력은 여러 개의 테스트 케이스로 이루어져 있습니다.

첫 번째 줄에 테스트 케이스의 개수 가 주어집니다.