There is a staircase with n steps. You need to reach the top and you can either climb 1 step or 2 steps at a time.

In how many distinct ways can you reach the top of the staircase.

Examples

n: 2
Answer: 2
Explanation: [[1, 1], [2]]

n: 4
Answer: 5
Explanation: [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• Two space-separated integers ‘n’ and ‘target’.
• n space-separated integers denoting the available denominations.

Output Format

For each test case, the output contains a line with one integer denoting the number of possible combinations.

Sample Input

3
2
3
4

Expected Output

2
3
5

Constraints

1 <= T <= 45
1 <= n <= 45