题目描述

塔子哥有一个长度为n且值都为0的数组a。对于这个致组塔子哥每次操作可以选择一个区间[l, r]，对于[l,r]上的每一个数牛必须让其加一或者乘二(元素之间操作独立，可以选择些元素乘二，一些元素加一，但是区间内每个元素都要操作)

塔子哥还有一个目标数组b，塔子哥想知道对于初始数组a来说，其最少操作多少次可以将其变为b呢。

输入描述

第一行为，表示有t组数据

接下来有2t行，每组数据的第一行为一个n，第二行为n个整数，表示目标数组的元素b $1<=t<=10, 1<=n<=10^5, 1<=b_i<=10^9, \sum n<=10^5$

输出描述

输出为t行，每行为一组答案表示塔子哥的最小操作次数

样例

输入

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

输出

2
4

说明 说明 第一组数据中，塔子哥第一次选择区间[1,5]，让区间内所有元素加一，第二次塔子哥选择区间[3,3]，让元素乘二。

第二组数据中，塔子哥第一次选择区间(1,5]，让区间内所有元素加一。第二次塔子哥选择区间[2,5]，让区间元素加一。第三次塔子哥选择区间[3,5]，让a3加一，让a4,a5乘二。第四次塔子哥选择区间[5,5]，让元素加一