CDGLF3 - Mr Phoenix And OR Operation

Mr Phoenix And OR Operation

 

Mr Phoenix has a sequence of ‘n’ non negative integers: A1,A2,A3,...,An. Mr CSI-DTU has invented a function F(l,r) {l,r, are non negative integers such that 1<=l<=r<=n)} and F(l,r)=Al | A(l+1) | A(l+2) |...| Ar. ie bitwise OR of all the elements with indexes from l to r.(both inclusive)

Now, Mr Phoenix has decided to calculate the values of F(l,r) for all l, r such that 1<=l<=r<=n and he wants to know how many distinct values are there of F(l,r) . Help Mr Phoenix in finding out that count.

 

Input

First line of input consists of ‘T’-number of test cases. First line of each test case consists of ‘n’-number of elements of the array and the second line consists of ‘n’ numbers .

 

Output

Print the desired value corresponding to each test case on a single line.

 

Constraints

1<=T<=50

1<=n<=10^5

0<=Ai<=10^6

 

Sample Input

2

3

1 2 0

5

0 1 2 0 4

 

Sample Output

4

7


 


Added by:CSI
Date:2015-02-12
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-02-16 06:18:48 Mitch Schwartz
Time limit is tight for slower languages, maybe not possible to get AC in some (e.g. Ruby is generally slower than Python 2.7, and I barely passed in time with that). I think increasing time limit to accommodate slower languages would not allow bad complexity to pass in faster languages.

Last edit: 2015-02-16 07:14:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.