144. Shuffling

Problem Statement:
Jack loves to play with cards, once he was playing with a deck of uniquely numbered cards, the game was to sort the cards by their numbers (in increasing order).

Now he shuffled all the cards and put them in a single row on a table, and before starting to sort them he wanted to count the number of cards which will stay at the same position after the sorting. To sort the cards, he will keep swapping pairs of cards as necessary until the cards are sorted in increasing order from left to right.

Given the initial cards order, can you help Jack to count the number of cards as described above?

Input Format:
The first line of the input will contain an integer T, the number of test cases. Followed by T test cases, each test case starts with a line containing an integer N (1 ≤ N ≤ 10,000) which is the number of cards in this test case, followed by a line which contains N space separated integers which represent the numbers on the cards on the table before sorting them (from left to right).

Output Format:
For each test case, print one integer that indicate the number of cards which will stay in their original positions.

Sample Input:
1 5 5 8 1 9 10

Sample Output:
2

 Added by: alaa.jrad Added at: 2014-03-05 19:00:40 UTC Time Limit: 2 seconds Partial score: No Source: Tishreen University First Training Contest 2014