F-小苯的优雅好序列_牛客周赛 Round 70

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

题目描述

小苯认为满足以下任一条件的序列 $a$ 是优雅的。
$\bullet\ |a|=1$ 。

$\bullet$ 对于所有 $i\ (1 \leq i \leq |a|)$ ，都存在 $j\ (1 \leq j \leq |a|, j \ne i)$ ，使得 $a_j | a_i$ 或 $a_i | a_j$ 。

小苯认为一个长度为 $n$ 的数组 $a$ 是好数组，当且仅当 $a$ 所有的连续子数组都优雅。即对于所有 $l, r\ (1 \leq l \leq r \leq n)$ ， $a_l, a_{l+1},\cdots,a_r$ 都是一个优雅的序列。

现在小苯有一个数组 $a$ 和正整数 $k$ ，他想知道有多少个不超过 $k$ 的正整数 $x\ (1 \leq x \leq k)$ ，都有： $a_1+x, a_2+x,\cdots,a_n+x$ 是一个好数组，请你帮他算一算吧。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行两个正整数 ，表示数组 的长度。
第二行  个整数 ，表示数组 。
（保证所有测试数据中  的总和不超过 。）

输出描述:

输出  行，每行两个整数 ，分别表示不同的  数字个数，以及这些  的和。

示例1

输入

复制

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

输出

复制

3 8
0 0
100 5050

说明

对于第一组测试数据，存在 ，这  个合法的数字，他们的和是 。