{"problem":{"name":"Divisibility Homomorphism","description":{"content":"We call an infinite sequence of positive integers $(a_1,a_2,\\cdots)$ **good** if and only if it satisfies both of the following conditions: *   There exists a finite constant $C$ such that $a_n \\le C","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc067_c"},"statements":[{"statement_type":"Markdown","content":"We call an infinite sequence of positive integers $(a_1,a_2,\\cdots)$ **good** if and only if it satisfies both of the following conditions:\n\n*   There exists a finite constant $C$ such that $a_n \\le C \\cdot n$ for all $1 \\le n$;\n    \n*   For all pairs of positive integers $(n,m)$, $a_n \\mid a_m$ if and only if $n\\mid m$. Here, $x \\mid y$ means $x$ divides $y$.\n    \n\nYou are given a positive integer sequence $A=(A_1,A_2,\\cdots,A_N)$ of length $N$. Check if there exists a good infinite sequence starting with $(A_1,A_2,\\cdots,A_N)$.\nYou have $T$ testcases to solve.\n\n## Constraints\n\n*   $1\\le T \\le 5000$\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A_i \\leq 10^{18}$\n*   The sum of $N$ across the test cases in a single input is at most $5000$.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc067_c","tags":[],"sample_group":[["5\n5\n1 2 3 4 5\n5\n1 4 9 16 25\n5\n1 4 6 8 10\n5\n1 2 4 4 5\n5\n1 2 3 5 4","Yes\nYes\nYes\nNo\nNo\n\nFor the $1$\\-st test case, we can let $a_n=n$ and that satisfies the condition."]],"created_at":"2026-03-03 11:01:14"}}