Flip The Bits Problem Statement

Given a binary string S of length N where initially all characters are '1', perform exactly M operations, choosing from four specific operations, and determine how many distinct final strings are possible.

Operations:

• If the chosen number is 1, flip all characters in the string.
• If the chosen number is 2, flip all characters at odd indexes.
• If the chosen number is 3, flip all characters at even indexes.
• If the chosen number is 4, flip all characters at (3k + 1) indexes.

Input:

The first line contains an integer 'T' representing the number of test cases. 
Each test case consists of a line with two space-separated integers N and M representing the size of the string and the number of operations.

Output:

For each test case, print a single integer indicating the number of distinct final strings possible after M operations. Print the output of each test case on a new line.

Example:

Input:

2
3 2
4 3

Output:

3
4

Constraints:

• 1 <= T <= 5
• 1 <= N, M <= 5000

Note:

You do not need to handle input or print output. Implement the function to return the number of distinct final strings.