给定一个正整数，我们希望通过一些操作把它变成正整数。操作流程如下：初始数字为，每次可以将当前的数字乘以，或者除以。除以时上取整或者下取整由你决定（输入给定）。 形式化地：初始时执行，每次操作执行，,中的一种，最后要让的值等于 问至少需要几步操作（或者不可能达成）？

输入描述:

第一行一个正整数，表示数据组数。接下来行，每行三个正整数

输出描述:

对于每组数据，如果有解输出最少的操作数，否则输出