405893: GYM102152 K Subarrays OR

A bitwise OR takes two equal-length binary representations and performs the logical OR operation on each pair of the corresponding bits. The result in each position is $$$0$$$ if both bits are $$$0$$$, while otherwise, the result is $$$1$$$. The bitwise OR operation is represented in this problem, and also in programming languages such as C++ and Java, using the operator "|".

To get the value of $$$x\,|\,y$$$, consider both numbers in the binary representation (padded with zeros to make their lengths equal), then apply the OR operation on the corresponding bits, and return the result into decimal form. For example, the result of $$$10\,|\,17$$$ = $$$01010\,|\,10001$$$ = $$$11011$$$ = $$$27$$$.

You are given an array $$$a$$$ of $$$n$$$ integers. A subarray of the array $$$a$$$ is a sequence $$$a_l, a_{l + 1}, \cdots, a_r$$$ for some integers ($$$l,\,r$$$) such that $$$1 \le l \le r \le n$$$.

The subarray OR is defined as the the bitwise OR of all elements inside that subarray. Formally, the subarray OR of the subarray ($$$l,\,r$$$) is $$$a_l\,|\,a_{l + 1}\,|\,\cdots\,|\,a_r$$$.

Your task is to find the subarrays OR values of all subarrays in the given array and return the number of unique values among them. Can you?

The first line contains an integer $$$T$$$ ($$$1 \le T \le 5$$$) specifying the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) giving the size of an array $$$a$$$. Then a line follows contains $$$n$$$ integers $$$a_1, \cdots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), giving the array $$$a$$$.

For each test case, print a single line containing the number of unique subarrays OR values among the subarray OR values of all subarrays in the given array.

2
3
1 2 3
3
2 4 8

3
6

In the first test case, there are $$$6$$$ subarrays in the given array $$$a$$$. The subarray OR of these subarrays is calculated as follows:

1. ($$$1,\,1$$$) $$$\rightarrow$$$ $$$1$$$.
2. ($$$1,\,2$$$) $$$\rightarrow$$$ $$$1\,|\,2 = 3$$$.
3. ($$$1,\,3$$$) $$$\rightarrow$$$ $$$1\,|\,2\,| 3 = 3$$$.
4. ($$$2,\,2$$$) $$$\rightarrow$$$ $$$2$$$.
5. ($$$2,\,3$$$) $$$\rightarrow$$$ $$$2\,|\,3 = 3$$$.
6. ($$$3,\,3$$$) $$$\rightarrow$$$ $$$3$$$.

So, the number of unique values among all subarrays is $$$3$$$.