# DCP-489: Country Roads Back to All Problems

Hard Divide and Conquer > Dynamic Programming

In a country there are **N** cities. The cities are numbered from **1** to **N**. There is a road from city **i+1** to **i** for all **i (1 ≤ i < N)**. The roads are uni-directional. The minister of the country decided to construct some more roads based on the array **A**. A road will be built from city **i** to city **j** where **(j < i)** if **( j ≥ A[i] )** and **gcd(i , j) > 1**. City number **1** is the capital of this country. Mr. Riki is currently staying at the **N** th city. He wants to go to the capital. You have to tell the minimum number of cities he has to visit (including **N** th city) to reach the destination. Input: ------ The first line contains an integer **T (1 ≤ T ≤ 5)**, denoting the number of test cases. Each case contains an integer **N (3 ≤ N ≤ 100000)** denoting the number of cities. The next line will contain **N** integers separated by spaces, denoting the elements of the array **A**. For any city **i** , (**1 ≤ A[i] ≤ i**). Output: ------- For each test, print the answer in a single line. Sample Input ------------ 2 5 1 1 2 2 4 6 1 2 3 4 5 1 Sample Output ------------- 4 3 **Test Case 1**: ![City Road Map][1] Here is the country road map. In the path **5 -> 4 -> 2 -> 1** , Mr. Riki has to visit **4** cities ; which is the minimum. **Test Case 2**: ![enter image description here][2] Here is the country road map. In the path **6 -> 2 -> 1** , Mr. Riki has to visit **3** cities ; which is the minimum. [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/b3d73cb6-fc86-cd01-0255-08d578e59eb1_f9aa2603ee724cc085518c1692e2521c_W323xH324.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/96570011-764b-cfc8-9e0c-08d57a3b736d_c27d53f5de4f4c5098fa42cc4192af07_W317xH323.png

### Problem Limits

 Language Time Limit (seconds) C 3.00 C++ 3.00 C++14 3.00 C# 6.00 Go 6.00 Java 6.00 JavaScript 6.00 Objective-C 6.00 Perl 6.00 PHP 6.00 Python 6.00 Python3 6.00 Ruby 6.00 VB.Net 6.00

# 14/139

Solve/Submission

### Ranking

# User Language Timing
01 ovis96 Cpp14 0.49s
02 Morass Cpp14 0.95s