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 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 ≤ 105, 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 ≤ Di ≤ 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*106

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

Added by:Morass
Date:2016-09-16
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2021-03-21 12:35:33
Understanding problem itself took me long time, but nevertheless good problem :)
2019-08-15 09:21:03
Any tips??
2016-09-17 07:45:18
@:D: Yay thanx man! Very nice to hear! So glad somebody likes it!! :P ^_^
2016-09-17 02:27:39 :D
Fun problem. Thank's for setting up this one and the others from ADA series.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.