# Count the number of all possible binary strings without consecutive 1’s

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 = b = 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}

}

``````