Contents

# Click Here!

You are given an undirected graph with NN nodes (numbered 11 through NN). For each valid ii, the ii-th node has a weight WiWi. Also, for each pair of nodes ii and jj, there is an edge connecting these nodes if jiWjWij−i≠Wj−Wi.

Find the number of connected components in this graph.

### Input Format Just a Graph solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers W1,W2,,WNW1,W2,…,WN.

### Output Format Just a Graph solution codechef

For each test case, print a single line containing one integer — the number of connected components in the graph.

### Constraints

• 1T1041≤T≤104
• 1N1051≤N≤105
• |Wi|109|Wi|≤109 for each valid ii
• the sum of NN over all test cases does not exceed 21052⋅105

### Subtasks Just a Graph solution codechef

Subtask #1 (30 points):

• N103N≤103
• the sum of NN over all test cases does not exceed 21032⋅103

Subtask #2 (70 points): original constraints

### Sample Input 1

2
2
1 2
2
2 1


### Sample Output 1  Just a Graph solution codechef

2
1


### Explanation

Example case 1: For i=1i=1 and j=2j=2, we have 21=212−1=2−1, therefore there are no edges in the graph and there are two connected components.

Example case 2: For i=1i=1 and j=2j=2, we have 21122−1≠1−2, therefore there is an edge between 11 and 22, the graph is connected, so there is only one connected component.