Counting Cafeteria Menus

Time limit2sMemory limit256 MB

Summary

Count how many distinct dish sets appear when the current set of N out of M dishes shifts forward by one each meal.

Level: Medium5 of 10
Topics: String matching, Array, Math
Solved: No attempts yet

Problem

The company cafeteria can cook $M$ different dishes, numbered 1 through $M$ .

At every meal the cafeteria puts out $N$ of those dishes, and each employee eats one of them. The dishes served at a meal are decided by this rule.

If dish $K$ was served at the previous meal, dish $K+1$ is served at this meal. If dish $M$ was served at the previous meal, dish 1 is served at this meal.

So every served number moves up by one from one meal to the next, and the number after $M$ wraps back to 1. Meals go on forever, so every menu you can reach by shifting this meal's menu again and again is served sooner or later.

Younghee just joined the company and wants to know how many different menus the cafeteria serves. She tells you the dish numbers served at this meal. Count the different menus. Two menus are the same when they hold exactly the same dish numbers.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 20$ )

The first line of each test case contains $M$ , the number of dishes the cafeteria can cook, and $N$ , the number of dishes served at one meal. ( $1 \le N \le M \le 10^6$ )

Each of the next $N$ lines contains one dish number $x_i$ served at this meal. ( $1 \le x_i \le M$ ) The numbers are distinct and sorted in increasing order.

The sum of $M$ over all test cases is at most $10^6$ .

Output

For each test case, print the number of different menus on its own line.

Examples4

Example 1
Input
```
2
6 3
1
3
5
16 4
1
3
9
11
```
Expected output
```
2
8
```
Example 2
Input
```
1
1 1
1
```
Expected output
```
1
```
Example 3
Input
```
1
10 10
1
2
3
4
5
6
7
8
9
10
```
Expected output
```
1
```
Example 4
Input
```
1
7 1
4
```
Expected output
```
7
```