Sherlock Holmes has decided to start a new academy to some of the young lads. He has conducted several tests and finally selected N equally brilliant

students.Now he don't know whether to train all the N students or not. Now since Holmes was in a confusion, Watson came up with an idea. He wanted to

test the obedience of the students. So during the camp, the students were given some Swiss Chocolates as gifts each time when they passed a level.Now some of them have

finished eating all the chocolates, some of them had some remaining. Now to test their team chemistry and IQ skills, Watson told the lads to arrange themselves in such 
a way that,  number of chocolates of the ith kid should be equal to the sum of   (i-1)th kid and (i-2)th kid. Now they have arranged themselves in an order.
Now Sherlock announced that he will select the students who have formed the line according to this order. But since there can be many such small groups among the

entire N kids, he will select a sequence of kids such that the length of the sequence is maximized, meanwhile satisfying the above condition 

-----Input-----
First line is an integer T which denotes the total number of test cases. Each of the next T lines contains an integer N which denotes, N students. The next 
line contains N spaced integers.where it denotes the order in which the kids arranged themselves. 

-----Output-----
Each line contains an integer which denotes the maximum number of students among the N students who have arranged themselves according the rule said by Watson.It is guaranteed that Holmes will select atleast 1 or 2 students

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10^5
- 1 ≤ Each of next N integers ≤ 10^9

-----Subtasks-----
Subtask #1 : (20 points)
- 1 ≤ T ≤ 10
- 1 ≤ N≤ 100
- 1 ≤ Each element≤ 10^3

Subtask 2 : (80 points) 

- 1 ≤ T ≤ 10
- 1 ≤ N≤ 100000
- 1 ≤ Each element≤ 10^9

-----Example-----
Input:
2
5
2 3 5 1 2
3
1 2 3

Output:
3
3

-----Explanation-----
Example case 1. Here the first kid has 2 chocolates, second has 3 chocolates, third kid has 5 chocolates, which is the sum of first kid's total chocolates 
and second kid's chocolate. Forth student has only 1 chocolate where he did not follow the rule. So the maximum number of kids who arranged themselves in the order was 
3. That is students at index 1 to index 3.

Difficulty: interview

Starter code:

Solutions:
t = eval(input())

for i in range(t):
 n = eval(input())
 a = list(map(int, input().split()))
 cnt = 2
 cnt1 = 2
 ll = len(a)
 if ll < 3:
  cnt1 = ll
 else:
  for j in range(2,ll):
   if a[j-1] + a[j-2] == a[j]:
    cnt += 1
    cnt1 = max(cnt1, cnt)
   else:
    cnt1 = max(cnt1, cnt)
    cnt = 2
 print(cnt1) 

t = int(input())

for e in range(t):
 n = int(input())
 chocolates = input().strip().split(" ")

 # Sequence is working
 sequence = []
 for x in range(len(chocolates) - 2):
  if int(chocolates[x]) + int(chocolates[x+1]) == int(chocolates[x+2]):
   sequence.append(1)
  else:
   sequence.append(0)

 inSequence = 0
 gSequence = 0
 end = 0
 for x in range(len(sequence)):
  if sequence[x] == 1:
   inSequence += 1
   if x == len(sequence) - 1:
    end = x + 1
    gSequence = inSequence
  else:
   if inSequence > gSequence:
    gSequence = inSequence
    end = x
   inSequence = 0

 space = " "
 output = chocolates[end - gSequence:end + 2]
 print(len(output))

t = int(input())

for e in range(t):
 n = int(input())
 chocolates = input().strip().split(" ")

 # Sequence is working
 sequence = []
 for x in range(len(chocolates) - 2):
  if int(chocolates[x]) + int(chocolates[x+1]) == int(chocolates[x+2]):
   sequence.append(1)
  else:
   sequence.append(0)

 inSequence = 0
 gSequence = 0
 end = 0
 for x in range(len(sequence)):
  if sequence[x] == 1:
   inSequence += 1
   if x == len(sequence) - 1:
    end = x + 1
    gSequence = inSequence
  else:
   if inSequence > gSequence:
    gSequence = inSequence
    end = x
   inSequence = 0

 space = " "
 output = chocolates[end - gSequence:end + 2]
 print(len(output))

for _ in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 mx = 1
 if n > 1 and a[0] == a[1]:
  mx = 2
 if n > 2:
  c = 1
  f = 1
  for i in range(2, n):
   if a[i] == a[i-1] + a[i-2]:
    c += 1 + f
    f = 0
    continue
   else:
    mx = max(c, mx)
    c = 1
    f = 1
  mx = max(c, mx) 
 print(mx) 

for _ in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 mx = 1
 if n < 3:
  if n == 2 and a[0] == a[1]:
   mx = 2
 else:
  c = 2
  for i in range(2, n):
   if a[i] == a[i-1] + a[i-2]:
    c += 1
    continue
   else:
    mx = max(c, mx)
    c = 2
  mx = max(c, mx) 
 print(mx)

for _ in range(eval(input())):
 n = eval(input())
 A = list(map(int, input().split()))
 if n < 3:
  print(n)
 elif n == 3:
  print(2 if A[2] != A[0] + A[1] else 3)
 else:
  st = 1
  max_len = 0
  for i in range(2,n):
   if A[i] != A[i-1] + A[i-2]:
    max_len = max(max_len, i-st)
    st = i
  max_len = max(max_len, (i-st)+1) if st < n-1 else max_len
  print(max_len + 1)

tc = int(input())
while tc!=0:
 size = int(input())
 data = [] 
 data = list(map(int,input().split()))
 if size == 1:
  print("1")
  tc -= 1
  continue
 i = 2
 count = 2
 max = 2
 while i < size:
  if data[i] == (data[i-1] + data[i-2]):
   count+=1
   if count > max:
    max = count
  else:
   count = 2
  i+=1
 print(max)
 tc -= 1 

tc = int(input())
while tc!=0:
 size = int(input())
 data = [] 
 data = list(map(int,input().split()))
 i = 2
 count = 2
 max = 2
 while i < size:
  if data[i] == (data[i-1] + data[i-2]):
   count+=1
   if count > max:
    max = count
  else:
   count = 2
  i+=1
 print(max)
 tc -= 1

tc = int(input())
while tc!=0:
 size = int(input())
 data = [] 
 data = list(map(int,input().split()))
 i = 2
 count = 2
 max = 0
 while i < size:
  if data[i] == (data[i-1] + data[i-2]):
   count+=1
   if count > max:
    max = count
  else:
   count = 2
  i+=1
 if count > max:
  max = count
 print(max)
 tc -= 1

for _ in range(int(input())):
 n=int(input())
 s=list(map(int,input().split()))
 maxx=0
 count=0
 if n<=2:
  print(n)
 elif n==3:
  if s[2]==s[1]+s[0]:
   print(3)
  else:
   print(2)
 else:
  for i in range(2,n):
   if s[i]==s[i-1]+s[i-2]:
    count+=1
    maxx=max(maxx,count)
   else:
    count=0
  print(maxx+2)
  
  



import sys

for __ in range(eval(input())) :
 n = eval(input())
 lists = list(map(int,sys.stdin.readline().split()))
 curmax , temp , fflag = 0 , 2 , False
 for i in range(2,n) :
  if lists[i-2]+lists[i-1] == lists[i] :
   temp += 1
  else :
   if temp > curmax :
    curmax = temp
   temp = 2
 print(max(curmax,temp) if n > 1 else 1)


import sys

for __ in range(eval(input())) :
 n = eval(input())
 lists = list(map(int,sys.stdin.readline().split()))
 curmax , temp , fflag = 0 , 2 , False
 for i in range(2,n) :
  if lists[i-2]+lists[i-1] == lists[i] :
   temp += 1
  else :
   if temp > curmax :
    curmax = temp
   temp = 2
 print(max(curmax,temp))


for t in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 if (n==1):
  print(1)
 elif (n==2):
  print(2)
 else:
  c = 2
  m = 0
  for i in range(2,n):
   if (a[i] == a[i-1]+a[i-2]):
    c+=1
   else:
    m = max(c,m)
    c = 2
  m = max(c,m)
  print(m)

for t in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 c = 2
 m = 0
 for i in range(2,n):
  if (a[i] == a[i-1]+a[i-2]):
   c+=1
  else:
   m = max(c,m)
   c = 2
 m = max(c,m)
 print(m)