Notes: The input part of the problem statement is missing the following information: The problem begins with number on a line by itself indicating the total number of test cases. Since the sample input is wrong, this has been uploaded on uDebug.