사랑의 상처

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

저택의 꽃밭에는 셰리가 좋아하는 $N$가지 색깔의 장미가 자라고 있었어요. 이 꽃밭에는 사시사철 꽃이 계속 자라는 마법이 걸려 있어서, 각 색깔의 장미는 무한히 많은 것이나 다름없었죠. 어느 날, 셰리는 장미를 몇 송이 따서 리본으로 묶어 소중한 친구를 위한 꽃다발을 만들어 보려고 했어요.

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

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

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

첫 번째 줄에 테스트 케이스의 개수 $Q$가 주어집니다. $(1 \leq Q \leq 100)$

두 번째 줄부터 한 줄에 하나씩 테스트 케이스가 주어집니다.

각 테스트 케이스에는 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어집니다. $(1 \leq N \leq 100;$ $\boldsymbol{N \lt M \leq {10}^8};$ $0 \leq K \leq {10}^{16})$

각 테스트 케이스마다 꽃다발을 구성할 수 있는 장미의 최대 개수를 한 줄에 하나씩 출력합니다.