Suppose A and B are candidates foroffice and there are 2 n voters, n of whom votefor A and n for B.
Suppose A and B are candidates foroffice and there are 2
n voters,
n of whom votefor A and
n for B. Write an algorithm to count the numberof ways the ballots can be counted so that, at any point during thecounting process, A is always ahead of or tied with B. Ballots fora given candidate are indistinguishable. For example, for 4 voters,AABB is a valid counting and ABBA is not.
Input Description The input will be a sequence of testcases. The first line presents the number of test cases. The casesthemselves begin with the second line. Each test case presents
half the number of voters,
n, where
n ?30.
OutputDescription For each test case, the output shouldappear on a separate line. For each test case, print the number ofways the ballots can be counted so that A is always ahead of ortied with B.
Sample Input 4 1 2 3 5
Sample Output 1 2 5 42 Requirements: Show answer using pseudo code and add brief explanations of youralgorithm. Show the time complexity of your algorithm. . . .