Beautiful Sequence

题号：NC296716
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 由于经常做不出 $\gcd$ 题，因此小苯不喜欢 $\gcd$ ，所以小苯认为：数组的 $\gcd$ 不存在于数组中的话，则该数组是美丽的。

$\hspace{15pt}$ 他现在有一个长度为 $n$ 的序列 $a$ ，请你帮他算一算， $a$ 中有多少个非空子序列（不要求连续）是美丽的数组吧。

$\hspace{15pt}$ 【子序列】：子序列为从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。

$\hspace{15pt}$ 【数组的 $\gcd$ 】：即数组中所有数字的最大公约数。（特别的，只有一个元素的话，则该数组 $\gcd$ 就等于这个元素的值。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示序列  的长度。
第二行  个正整数 ，表示序列 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：

在单独的一行输出一个整数，表示 "美丽的" 子序列个数。
（由于答案可能很大，因此输出其对  取模后的值。）

示例1

输入

复制

2
6
1 2 3 4 5 6
3
2 2 2

输出

复制

22
0

说明

对于第二组测试数据，显然不存在这样的子序列，因此输出 。