Description

给你三个正整数 $n$、$idx$ 和 $max$ 。你需要构造一个同时满足下述所有条件的数组 $arr$（下标从 0 开始计数）：

• $arr$的长度为$n$。
• $arr$的每个元素都为正整数。
• $arr$中任意两相邻元素之差的绝对值小于等于$1$。
• $arr$中元素的总和不超过$max$。
• $arr[idx]$值要被最大化。

求$arr[idx]$的值。

Input Format

第一行输入一个正整数$t(1≤t≤1000)$，表示有$t$组测试样例。

每组样例输入一行，分别输入三个正整数$n,idx(1≤index＜n)$ 和 $max(1≤n≤max≤10^9)$ 。

Output Format

对于每组样例：

输出一行，包含一个正整数，表示$arr[idx]$的值。

2
4 2 6
6 1 10

2
3

Source

Online Judge http://127.0.0.1