人们常对生活有各种各样的解读。有些人走得顺风顺水，在最高峰处发现了生活的意义；而有些人则屡遭不幸，感叹生活如落雪般转瞬即逝，却又在困境中奋力燃烧以求转机。

无论如何，生活是错综复杂的，充满了值得探索的美好事物。对于像你们这样的程序员来说，将生活概念化为一场无限图的旅行是合理的——准确地说，这是一个由无限数量的顶点和边组成的图。它的顶点表示生活的所有可能性，从 $0$ 开始编号。对于每一对无序顶点 $u$ 和 $v$，如果 $u$ 和 $v$ 的二进制表示恰好有一位不同（假设该位是从低到高第 $w$ 位），则它们之间存在一条权重为 $w$ 的无向边。例如，权重为 $3$ 的无向边 $(2, 6)$ 在图中存在，因为 $2 = (10)_2, 6 = (110)_2$，第三位是唯一不同的位；但边 $(5, 6)$ 不存在，因为 $5 = (101)_2, 6 = (110)_2$，它们的二进制表示有两位不同。

起初，你站在顶点 $s$ 上，你相信真爱（不一定是某个人）应该存在于顶点 $t$ 上。于是你开始从黎明到黄昏在生活中寻找真爱的旅程。每一刻，你都对自己当前所在的顶点感到不满，并决定离开它。因此，在所有连接到该顶点的边中，你选择权重最小的一条，沿着它移动到另一个顶点，并永久地从图中切断这条边（嗯，这看起来像是发誓再也不回来）。由于旅程是无止境的，且对真爱的信念是无限的，你开始对第 $k$ 次到达顶点 $t$ 的时间感兴趣（特别地，初始状态被视为你第 $1$ 次到达顶点 $s$）。求出你在旅程中切断的边数，对 $10^9 + 7$ 取模，或者报告无法第 $k$ 次到达顶点 $t$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，唯一的一行包含三个整数 $s, t, k$ ($0 \le s, t < 2^{10^6}, 1 \le k \le 10^9$)，其中 $s, t$ 以二进制表示给出（不含额外的前导零），$k$ 以十进制表示给出。

保证所有测试用例中二进制表示长度之和不超过 $10^7$。

输出格式

对于每个测试用例，如果无法第 $k$ 次到达顶点 $t$，则输出 $-1$。否则，输出你切断的边数，对 $10^9 + 7$ 取模。

样例

输入 1

4
1 10 1
1 10 2
100 0 2
11 11 3

输出 1

2
-1
9
20

说明

在第一个测试用例中，你通过路径 $1 \xrightarrow{w=1} 0 \xrightarrow{w=2} 2$ 第一次到达顶点 $2$，因此切断了 $2$ 条边。同样，从顶点 $1$ 开始，可以证明一旦你在第一次到达顶点 $2$ 时离开它，你就永远不会再回来了。因此，第二个测试用例的答案是 $-1$。