小苯的美丽区间_牛客题霸

小苯认为一个数是美丽数，当且仅当：如果将不停除以，直到不整除时停止，此时恰好等于。如果一个数美丽，则其美丽值为：以上操作中除以的次数。否则一个数不美丽，则其美丽值为。现在小苯有一个长度为的数组，他想知道中所有连续子数组的和的美丽值之和是多少，请你帮他算一算吧。形式化的：记数字的美丽值为，则请你求出。（其中表示数组在这一段区间的所有元素之和。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：第一行输入一个正整数 ，表示数组 的长度。第二行 个正整数 ，表示数组 。（保证同一个测试文件中的测试数据里， 的总和不超过 。）

输出描述:

对于每个测试数据，在单独的一行输出一个整数表示答案。

示例1

输入

输出

15
13

说明

对于第二组测试数据：；
所有长度为  的子区间和都是美丽的，因为  的二进制中只有一个 ，其美丽值为 ，因此总美丽值为 ；
所有长度为  的子区间和都是美丽的，因为他们的和都是 ， 的美丽值为 ，其总美丽值为 。
所有长度为  的子区间和都不是美丽的，因此美丽值总和为 。
唯一一个长度为  的子区间和是美丽的，其总和为 ，美丽值为 ；
综上，所有区间的总美丽值之和为：。