B'Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game. The joyboard has a screen containing n+1 slots numbered from 1 to n+1 from left to right. The n+1 slots are going to be filled with an array of non-negative integers [a_1,a_2,a_3, ldots,a_{n+1}] . Chaneka, as the player, must assign a_{n+1} with an integer between 0 and m inclusive. Then, for each i from n to 1 , the value of a_i will be equal to the remainder of dividing a_{i+1} (the adjacent value to the right) by i . In other words, a_i = a_{i + 1} bmod i . Chaneka wants it such that after every slot is assigned with an integer, there are exactly k distinct values in the entire screen (among all n+1 slots). How many valid ways are there for assigning a non-negative integer into slot n+1 ? Each test contains multiple test cases. The first line contains an integer t ( 1 <= q t <= q 2 cdot10^4 ) -- the number of test cases. The following lines contain the description of each test case. The only line of each test case contains three integers n , m , and k ( 1 <= q n <= q 10^9 ; 0 <= q m <= q 10^9 ; 1 <= q k <= q n+1 ) -- there are n+1 slots, the integer assigned in slot n+1 must not be bigger than m , and there should be exactly k distinct values. For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot n+1 . In the first test case, one of the 2 possible ways for Chaneka is to choose a_{n+1}=6 . If she does that, then: In the second test case, the 1 possible way for Chaneka is to choose a_{n+1}=0 . If she does that, then a = [0, 0, 0] . There is only 1 distinct value. In the third test case, there is no possible way for assig'...