You are provided an integers N. You need to count all possible distinct binary strings of length N such that there are no consecutive 1’s.Input Format

First line contains integer t which is number of test case. For each test case, it contains an integer n which is the the length of Binary String.Constraints

1<=t<=100 1<=n<=90Output Format

Print the number of all possible binary strings.Sample Input

2 2 3

Sample Output

3 5

Explanation

1st test case : 00, 01, 10 2nd test case : 000, 001, 010, 100, 101

## Solution

import java.util.*; public class Main { public static void main(String args[]) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); while(t-- > 0) { int n = scan.nextInt(); long[] a = new long[n]; long[] b = new long[n]; a[0] = b[0] = 1; for(int i=1;i<n;i++) { a[i] = a[i-1] + b[i-1]; b[i] = a[i-1]; } System.out.println(a[n-1]+b[n-1]); } } }

## Code Walkthrough

```
N = 3
a = {1, 0, 0}
b = {1, 0, 0}
for(int i=1;i<n;i++)
{
//i = 1
a[i] = a[i-1] + b[i-1]; // 2
b[i] = a[i-1]; //1
a = {1, 2, 0}
b = {1, 1, 0}
//i = 2
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
a = {1, 2, 3}
b = {1, 1, 2}
}
```