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

---

hide comments

	makhan_28: 2021-03-21 12:35:33 Understanding problem itself took me long time, but nevertheless good problem :)
	ahzong: 2019-08-15 09:21:03 Any tips??
	morass: 2016-09-17 07:45:18 @:D: Yay thanx man! Very nice to hear! So glad somebody likes it!! :P ^_^
	:D: 2016-09-17 02:27:39 Fun problem. Thank's for setting up this one and the others from ADA series.