ADAFENCE  Ada and Fence
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 kgon. Problem is, that there is only limited number or places (on circle) where pilars can be built. Ada has asked you, to find out the number of different regular kgon shaped fences which can be built on her land (two kgon's are considered different if they share NO common pillar).
Input
The first line will contain T, the number of testcases.Then T testcases follow, each beginning with two integers 3 ≤ K ≤ N ≤ 10^{5}, 3 ≤ K ≤ 100, the number of places where pillar can be built and number of edges of regular kgon
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 testcases won't exceed 2*10^{6}
Output
For each testcase print the number of different regular kgon 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
morass:
20160917 07:45:18
@:D: Yay thanx man! Very nice to hear! So glad somebody likes it!! :P ^_^ 

:D:
20160917 02:27:39
Fun problem. Thank's for setting up this one and the others from ADA series. 
Added by:  Morass 
Date:  20160916 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 