## GNYR09F - Adjacent Bit Counts

For a string of n bits x1,x2,x3,...,Xn the adjacent bit count of the string (AdjBC(x)) is given by

X1*X2 + X2*X3 + X3*X4 + ... + Xn-1 * Xn

which counts the number of times a 1 bit is adjacent to another 1 bit. For example:

Write a program which takes as input integers n and k and returns the number of bit strings x of n bits (out of 2ⁿ) that satisfy AdjBC(x) = k. For example, for 5 bit strings, there are 6 ways of getting AdjBC(x) = 2:
11100, 01110, 00111, 10111, 11101, 11011

### Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number (n) of bits in the bit strings, followed by a single space, followed by a decimal integer (k) giving the desired adjacent bit count. The number of bits (n) will not be greater than 100 and the parameters n and k will be chosen so that the result will fit in a signed 32-bit integer.

### Output

For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of n-bit strings with adjacent bit count equal to k.

### Example

```Input:
101 5 22 20 83 30 174 40 245 50 376 60 527 70 598 80 739 90 8410 100 90
```
```Output:
1 62 634263 18612254 1682125015 448747646 1609167 229373088 991679 1547610 23076518
```

 < Previous 1 2 3 4 5 Next > rishabh aggarwal: 2014-12-17 20:37:31 nice problem..... BLANKRK: 2014-05-17 21:05:21 nice one :D mystique_blue: 2013-10-31 08:32:34 This is what should be done: 1) Come up with a brute force solution.. 2) Alanlyze the recurisve statement to be used.. 3)Memoize it.. A few simpler test cases.. 1 5 1 --> 10 2 7 3 --> 16 3 7 4 --> 8 Pierre Boix: 2013-07-23 14:37:29 And if i have 11111. It's a solution, isn't it? Samer Dawalib: 2013-05-18 12:45:42 @Sanchit Manchanda 11011 11100 01110 00111 10111 11101 Balaji Ramasubramanian: 2013-01-14 03:24:43 @Sanchit Manchanda You can also have 11101 and 10111. Vaishnavh: 2013-01-04 09:34:06 Seems like the value of K is at most 90 :) Sanchit Manchanda: 2012-12-25 17:19:26 how n=5 and k=2 gives ans=6?? isn't it should be 4?? 11011 11100 01110 00111 for these, 01111=3,11110=3. not 2. can someone pls explain this test case?