Chef and Round Run

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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_{i}. Chef invented a definition of a magic box!
 Chef picks a box i and stays in front of it.
 Now Chef eats food from box i and skips next A_{i} boxes.
 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 spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the tastyness levels of each box.
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.
Here are Chef's paths if he starting from each the box:1>3>1 2>4>2 3>1>3 4>2>4As you see, all 4 boxes are magical.
Example case 2.
Here are Chef's paths if he starts from each box appropriately:1>1 2>3>4>1>1 3>4>1>1 4>1>1AS you see, only box 1 is magical.
Author:  berezin 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFRRUN 
Tags  aug16, berezin, graph, simple 
Date Added:  8042016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions