小红的bfs（hard）

题号：NC288879
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题与《小红的bfs（easy）》共享题目背景，两题的唯一区别在于，在本题中，小红只有在两数的最大公约数不等于 $1$ 时才可以移动。

$\hspace{15pt}$ 小红拿到了一个有 $n$ 个整数构成的排列，她初始站在第一个元素，她想移动到最后一个元素。小红移动的规则如下：
$\hspace{23pt}\bullet\,$ 若小红站在数字 $u$ 上，若 $u$ 和 $v$ 的最大公约数不等于 $1$ ，那么她可以花费 $1$ 的代价移动到数字 $v$ 。
$\hspace{15pt}$ 小红想知道，她移动到最后一个元素，最少需要花费多少代价？你还需要输出一个可行的移动方案。

$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个正整数  代表排列中的元素数量。 
第二行输入  个两两不同的正整数  代表排列中的元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。如果小红无法到达最后一个元素，直接输出 。

否则，请参考下方的格式输出。
第一行输出一个整数  代表需要花费的最小代价。
第二行输出  个整数 ，代表小红的移动路径中的元素下标。你需要保证  且 ，并且对于任意的 ， 和  满足  和  的最大公约数不等于 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

2
6
4 5 3 1 6 2
6
3 4 5 1 6 2

输出

复制

说明

对于第二组测试数据，首先从  移动到 ，然后从  移动到 。