该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

琪露诺得到了一个写在黑板上的P进制下长度为N的正整数X，这个正整数从左到右（从高位到低位）每一个数位上的数字分别为$A1，A2，A3……An(0≤Ai＜P)$。琪露诺刚好非常喜欢这个数字系统的所有数字，所以她希望能够将0 ~ P-1这些数字每个都至少出现一个。琪露诺一次可以进行以下操作：

将黑板上的正整数X的值加1，并将新的值X+1写在黑板上。

例如，当P = 5，N=3，X=234时。首先数字2，3，4已经出现了。

接下来琪露诺执行一次操作，X=240，这时候数字2，3，4，0已经出现了。

琪露诺再执行一次操作，X=241，这时候数字0，1，2，3，4都已经出现了。

现在请您编程计算琪露诺最少需要执行几次操作，就能让数字0 ~ P-1都出现至少一次。

Format

Input

第一行，一个整数q，$1≤𝑞≤2×10^3$，表示q组测试数据。

每组测试数据有两行。

每组第一行两个个整数N和P，有N个数位，是P进制$（1≤N≤100,2≤p≤10^9）$

每组第二行N个空格分隔的正整数Ai，表示正整数X的从左到右每个数位上的数字（0≤Ai≤P-1）。

数据保证正整数X没有前导0，即A1>0。

Output

每组测试数据输出一个整数，表示琪露诺最少花费几步就可以让0 ~ P-1都出现至少一次。很明显，每组数据总是有解的。

Samples

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

1
1
1

Limitation

1s, 1024KiB for each test case.