题目背景

我重生了，这个世界的馈赠，是一个能洞察人心的奇异坐标。

横轴衡量“乐观”与“悲观”，纵轴则掌控“理性”与“感性”。只要我愿意，就能在其中精确地找到任何人的投影。

前世，我因误解而与友人分道扬镳。这一世，用看清坐标带给我的，最精准的共情能力，我定会，修正那些后知后觉的遗憾。

题目描述

小排是一名重生者，他正在等待时间的倒流，计划着使用他的能力：

过去的一段时间长度为 $n$，每个时刻他都会遇到一个人，而他遇到的第 $i$ 个人的两项属性为 $a_i,b_i$。

他将在每个人面前表现出不同的态度 $c_i$。因为要修补一切遗憾，所以 $c_i\in\{a_i,b_i\}$。

小排期待着新生。定义一段时间 $[l,r]$ 的期待值为 $f(l,r)=$

其中 $k$ 为常数，$\mathrm{mex}(l,r)$ 表示 $c$ 的区间 $[l,r]$ 中未出现的最小自然数。

请你帮小排确定所有态度 $c$，以使得他在所有时间段 $i,j$ 的最大期待值 $\max f(i,j)$ 最大。

输入格式

第一行两个正整数 $tid,T$ 表示测试数据编号和测试数据组数。

对于每组数据：第一行输入两个数 $n,k$。

第二行输入 $n$ 个数表示序列 $a$。

第三行输入 $n$ 个数表示序列 $b$。

输出格式

对于每组数据，输出一行一个数表示期待值的最大值。

输入输出样例 #1

输入 #1

0 2
5 1
1 0 2 1 2
2 0 2 0 1
5 2
1 0 2 1 2
2 0 2 0 1

输出 #2

4
3

说明/提示

【样例解释 #1】

对第一组数据，一种可能的 $c$ 是 $\{2,0,2,0,2\}$，选择区间 $[1,5]$。

对第二组数据，一种可能的 $c$ 是 $\{1,0,2,1,1\}$，选择区间 $[3,5]$。

测试数据满足：

• 特殊性质 A：保证 $a_i<b_i$。
• 特殊性质 B：保证 $\forall 1\le i<n,a_i\le a_{i+1},b_i\le b_{i+1}$。
• 对于所有数据，满足 $T\le10,n\le2\times10^5,k\le10^9$。