Sadly, black holes are devouring our universe!
Cooper decided to embark on a mission in order to unravel the mysteries of black holes. Surprisingly, the scientist discovered a chain of wormholes via which he can travel. Given a list of worm holes, where the i-th worm hole leads to ai -th worm hole.
If he reaches the last worm hole (nth , considering 1 based indexing), he will be able to travel directly to the black hole, completing his objective.
As a statistician, it is now your responsibility to compute the likelihood that Cooper will reach the black hole if he chooses any of the worm holes at random.
The number of worm holes he can utilize to reach the end of the array will determine the probability of this event.
Print p+q if the probability is in the form p/q, where p and q are coprime.
Input:
The first line contains a single integer t (1≤t≤104) -- the number of testcases.
The first line of each testcase contains a single integer n (1≤n≤105) -- the total number of worm holes discovered.
The second line of each testcase contains n integers a1,a2,…,an (1≤ai≤n) -- .the worm hole index you can get to from the present worm hole.
Output:
Print an integer p+q where p/q is the probability, where p and q are coprime.
We can consider any worm hole to reach the end of the array in the first test case, therefore the probability is 2/2 = 1/1, hence p=1 and q=1. The 2nd worm hole is the end of the array (nth element, Considering 1 - based indexing); hence it will always be considered.
Similarly, in the second test case, we can only get to the end by using the first and fifth worm holes, therefore the probability is 2/5, so p=2 and q=5.
