镜像

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

题目描述

$\hspace{15pt}$ 对于一个正整数 $x$ ，小苯定义它的“镜像数”为将其十进制表示反转后得到的数（例如 $123$ 的镜像数是 $321$ ）。更具体地，若 $x$ 的十进制表示为 $x_1x_2\dots x_n$ ，则其镜像数为 $x_nx_{n-1}\dots x_1$ 。
$\hspace{15pt}$ 现在给定两个正整数 $a$ 和 $b$ ，小苯可以进行任意次操作（也可以不操作），每次操作从以下两种中任选一种执行：
$\hspace{23pt}\bullet\,$ 如果 $a$ 的个位数字不为 $0$ ，则将 $a$ 替换为它的镜像数；
$\hspace{23pt}\bullet\,$ 将 $a$ 加上 $k$ 。
$\hspace{15pt}$ 小苯想知道最少需要多少次操作，才能将 $a$ 变成 $b$ 。如果无法实现，输出 $-1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
输入三个正整数 ，表示给定的两个正整数以及操作的常数。
除此之外，保证单个测试文件的  之和、 之和均不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最少操作次数，若无法实现则输出 。

示例1

输入

复制

3
123 321 2
123 444 123
123 123 114514

输出

复制

1
2
0

说明

对于第一组测试数据，直接对  做镜像操作即可得到 ，需要  次操作。

对于第二组测试数据，其中一种最优方案是：
第一次操作：
第二次操作：
一共需要  次操作。

对于第三组测试数据，初始值已经满足，需要  次操作。

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。