Number of Ways to Reach Island N

Problem Statement

Number of Ways to Reach Island N Problem Description An archipelago has islands numbered 1, 2, 3, ... . One-way bridges connect them according to a single fixed rule: There is a bridge from island i to island j exactly when i < j and j is a multiple of i . (inferred -- the source shows the bridges only as a partly visible diagram; this is the one rule that matches every visible bridge and every route listed in the source's explanations, for example that the only routes to island 6 are 1 -> 6 , 1 -> 2 -> 6 and 1 -> 3 -> 6 .) So island 1 has a bridge to every other island, island 2 has bridges to 4, 6, 8, ... , island 3 has bridges to 6, 9, 12, ... , and so on. Bridges can only be crossed in their direction. A route to island N starts at island 1 , crosses bridges one after another, and ends at island N . When N = 1 the route that crosses no bridge counts (see Example 3). Two routes are different if they visit a different sequence of islands. You are given T independent