You are given array A consisting of N distinct integers. A set S of numbers is called fantastic if you can rearrange the elements in such a way that each element divides the next element in the order, i.e. S_i | S_{i + 1}, such that i < |S|, where |S| denotes size of set |S|.
Find out number of distinct fantastic sets that you can create using the values of the array. You can use one value only once in a particular set; ie. a set cannot have duplicate values. Two sets are said to be different from each other if there exists an element in one set, which does not exist in the other.
As the answer could be large, print your answer modulo 10⁹ + 7.

Input

First line of the input contains an integer T denoting the number of test cases. T test cases follow.
First line of each test case contains an integer N denoting number of elements in array A.
Next line contains N space separated integers denoting the elements of array A.

Output

For each test case, output a single line containing the corresponding answer.

Constraints

• 1 ≤ T ≤ 3
• 1 ≤ N ≤ 7.5 * 10⁵
• 0 ≤ A_i ≤ 7.5 * 10⁵
• All the elements of array A are distinct.