Ada the Ladybug owns a circular land. She wants to enclose it with fence. Anyway since nobody sells round planks, she has decided to fence it to shape of regular k-gon. Problem is, that there is only limited number or places (on circle) where pillars can be built. Ada has asked you, to find out the number of different regular k-gon shaped fences which can be built on her land (two k-gon's are considered different if they share NO common pillar).

Input

The first line will contain T, the number of test-cases.

Then T test-cases follow, each beginning with two integers 3 ≤ K ≤ N ≤ 10⁵, 3 ≤ K ≤ 100, the number of places where pillar can be built and number of edges of regular k-gon.

Afterward a line with N integers 1 ≤ D_i ≤ 100 follow, meaning the length of arc between two consecutive points where pillar can be built. The sum of all lengths will be divisible by K.

Sum of N over all test-cases won't exceed 2×10⁶.

Output

For each test-case print the number of different regular k-gon shaped fences which can be built.

Example Input

3
5 3
1 2 3 2 1
15 4
1 2 2 2 1 2 2 1 1 2 1 2 1 2 2
10 5
1 1 1 1 1 1 1 1 1 1

Example Output

1
1
2