红色的樱花

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

题目描述

牛牛和牛妹约好了一起去看樱花，这一天，他们如约而至的来到了樱花大陆上。

樱花大陆可以抽象成一个 ${n*m}$ 的二维棋盘，牛牛站在格子 ${(sx,sy)}$ ，牛妹站在格子 ${(ex,ey)}$ 。棋盘行的编号为 ${1,2,...,n}$ ，列的编号为 ${1,2,...,m}$ ，第 ${n}$ 行与第 ${1}$ 行相邻（即第 ${n+1}$ 行相当于第 ${1}$ 行），第 ${m}$ 列与第 ${1}$ 列相邻（即第 ${m+1}$ 列相当于第 ${1}$ 列）。现在牛牛要走到牛妹身边（即牛妹所在的格子），每次，他可以执行以下操作之一：

${1.}$ 选择一个任意的正整数 ${k}$ ，如果当前牛牛所在的格子为 ${(x,y)}$ ，移动到格子 ${(x+k,y+k)}$ ，此操作花费 ${a}$ 牛币。

${2.}$ 如果当前牛牛所在的格子为 ${(x,y)}$ ，移动到格子 ${(x+d,y)}$ ，此操作花费 ${b}$ 牛币。

${3.}$ 如果当前牛牛所在的格子为 ${(x,y)}$ ，移动到格子 ${(x,y+d)}$ ，此操作花费 ${c}$ 牛币。

确定牛牛是否可以走到牛妹的身边，如果能，计算牛牛所需要花费的最少的牛币数，否则输出 ${-1}$ 。

输入描述:

第一行一个整数，表示测试用例的组数。
接下来行每行个整数表示一组测试用例。

输出描述:

对于每组测试用例，输出一行一个整数表示答案。

示例1

输入

复制

2
3 3 3 1 1 2 2 1 1 1
3 3 2 1 1 3 3 8 1 1

输出

复制

1
2

题目描述

输入描述:

输出描述:

输入

输出

备注: