题目背景

@葛军 原创

古桥文乃作为一名 OIer，每天勤奋地在洛谷上刷题，然而她的父母却认为他有网瘾，就将她送到了杨叫兽的网戒中心。

一年之后，凭借不懈地努力古桥文乃终于逃了出来，并且立刻向警察蜀黍举报杨叫兽的所作所为，了解情况后警察请她带路去网戒中心抓捕杨叫兽。

题目描述

啊~~~~！

他们刚到达网戒中心就听到惨叫声从里面传来。古桥文乃在网戒中心呆了一年，对里面的情况很熟悉，立马就知道杨叔又在 $13$ 号治疗室“点现钱”。同时，她知道网戒中心有 $n$ 个房间，任意房间都有走廊相连，每个走廊和房间之间都有门，门是向外锁上的，且在开启后会自动锁上（即每次从房间 $i$ 进入任意一个与其相连的走廊需要花费 $c_i$ 的体力开锁，而从走廊进入房间不用耗费体力）。

杨叔为了防止“盟友”逃跑，在每个房间安装了摄像头，安排了 $n$ 个手下在监控中心看着监控。

特别的，$\bf1$ 号房间为监控中心，$\bf1$ 号手下负责防止任何人（除了杨叔）进入监控中心（否则立刻报告给杨叔），其余的 $2$ 号到 $n$ 号手下每人负责监控编号是自己整数倍的房间（例如 $n=10$ 时 $2$ 号手下监控 $2$ 号，$4$ 号，$6$ 号，$8$ 号，$10$ 号房间），$13$ 号治疗室也按照此规则被监控，如果他们其中一个人看到同一个人两次，就会向杨叔报告（但是每一个手下不会互相交流信息），好在这些手下都四肢发达头脑简单，只能记得上一秒的事情。

为了保证抓捕的顺利，古桥文乃和警察不能被发现，现在他们在 $x$ 号房间，$13$ 号治疗室在 $y$ 号房间，已知他们通过每一条走廊要 $1$ 秒，开锁和通过房间不用花费时间（但会被监控室的手下看到），古桥文乃和警察想知道他们在不被发现的情况下最少要花费多少体力才能进入 $13$ 号治疗室。

输入格式

本题多组询问。

第一行一个数 $T$，表示有 $T$ 组询问，第二行一个数 $n$，表示有 $n$ 个房间和手下（不过注意，本题中只读入一次 $n$，这个 $n$ 在每组数据中都是相同的）。

对于每一个询问，第一行两个数：$x,y$，其中 $x$ 表示古桥文乃和警察所在房间的编号，$y$ 表示 $13$ 号治疗室所在房间的编号，接下来一行 $n$ 个数，表示 $c_i$。

输出格式

输出共 $T$ 行，每个询问输出一行，仅一个数，表示在不被发现的情况下最少要花费多少体力才能进入 $13$ 号治疗室，若不能到达输出 $-1$。

1
5
2 4
1 2 3 4 5

5

提示

样例解释

一种可行的方案：$2\to3\to4$。

数据范围

对于 $30\%$ 的数据，$n\leq1500$，$T\leq15$；

对于 $50\%$ 的数据，$n\leq2500$，$T\leq30$；

对于 $70\%$ 的数据，$n\leq4500$，$T\leq50$；

对于 $100$ 的数据，$n\leq4500$，$T\leq200$，$2\leq x,y\leq n$，$c_i\leq9900$

提示：

本题读入可能较多，建议使用快读和 O2 优化。