In mathematics, Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers of the following integer sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence `F _{n}` of Fibonacci numbers is defined by the recurrence relation

And your task is to find Σ`F _{i}^{K}`, the sum of the

There are multiple test cases. The first line of input is an integer `T` indicates the number of test cases. For each test case:

There are two integers `N` and `K` (0 <= `N` <= 10^{18}, 1 <= `K` <= 100000).

提交代码