题目描述

现在规定一种漂亮的序列a（序列a的长度为s）需要满足如下任一条件：

(1)s==1,即序列a的长度是1。

(2)对于所有的i (1<=i<=s),都存在j(1<=j<=s,i!=j)，使得a[j]|a[i]或a[i]|a[j]（|为整除符号）。

小戴认为一个长度为n的序列a是好数组，当且仅当a所有的连续子数组是漂亮的，即对于所有l,r(1<=l<=r<=n)，a[l],a[l+1],...,a[r-1],a[r]都是漂亮的序列。

现在给定一个序列a和正整数k，小戴想知道有多少个不超过k的正整数x（1<=x<=k）,都有a[1]+x,a[2]+x,...,a[n]+x是一个好数组，请帮帮他吧。

输入格式

第一行一个正整数t，表示有t(t<=500)组测试数据。

对于每组测试数据：

第一行输入两个正整数n,k,分别表示序列a的长度和正整数k。

第二行n个整数a[1],a[2],...,a[n],分别表示序列a的值。

输出格式

共t行，每行两个整数cnt,sum,分别表示不同的x的个数，以及这些x的和。

30%的数据保证：1<=n<=5e4,1<=k<=100，1<=a[i]<=10000。

100%的数据保证：1<=n<=5e4,1<=a[i]<=1e9,1<=k<=1e9,t组数据n的总和不超过6e4。

输入/输出例子1

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

3 8
0 0
100 5050

样例解释

对于第一组测试数据，存在x=1,x=2,x=5,这3个合法的数字，他们的和是1+2+5=8。