Chef cooks nice receipes in the cafeteria of his company. The cafe contains

**N**boxes with food enumerated from**1**to**N**and are placed in a circle in clocwise order (boxes**1**and**N**are adjacent). Each box has unlimited amount of food with a tastyness level of**A**. Chef invented a definition of a magic box!_{i}- Chef picks a box
**i**and stays in front of it. - Now Chef eats food from box
**i**and**skips**next**A**boxes._{i} - Now Chef is staying at some other (probably even the same!) box and repeats.
- Box
**i**is a magic box if at some point of such game started from box**i**, Chef will find himself staying in front of it again.

When Chef came home, Chef's dog Tommy asked him about how many magic boxes were in the cafe? Help Chef to in finding that!

### Input

The first line of the input contains an integer

**T**denoting the number of test cases. The description of**T**test cases follows.
The first line of each test case contains a single integer

**N**denoting the number of boxes.
The second line contains

**N**space-separated integers**A**,_{1}**A**, ...,_{2}**A**denoting the tastyness levels of each box._{N}### Output

For each test case, output a single line containing number of magical boxes.

### Constraints

**1**≤ sum of all**N**over all the test cases in a single test file ≤**10**^{6}**0**≤**A**≤_{i}**10**^{9}

### Subtasks

**Subtask #1 (30 points):****1**≤ sum of all**N**over all the test cases ≤**10**;^{4}**1**≤**N**≤**1000****Subtask #2 (70 points):****1**≤ sum of all**N**over all the test cases ≤**10**;^{6}**1**≤**N**≤**10**^{5}

### Example

**Input:**
`3
4
1 1 1 1
4
3 0 0 0
4
0 0 0 2`
**Output:**
`4
1
2`

### Explanation

**Example case 1.**

**1**->**3**->**1**
**2**->**4**->**2**
**3**->**1**->**3**
**4**->**2**->**4**

As you see, all **4**boxes are magical.

**Example case 2.**

**1**->**1**
**2**->**3**->**4**->**1**->**1**
**3**->**4**->**1**->**1**
**4**->**1**->**1**

AS you see, only box **1**is magical.

ANSWER