该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

前言

停止向世界描绘你的监狱。

描述

多重集是一种允许元素重复的集合。熊猫有一个整数多重集 S 和三个整数 n, k, m。初始时，S = {1, 2, ...... , n}。熊猫希望对 S 执行一系列操作。在每次操作中：从当前的 S 中选择一个整数子集，使得该子集中所有整数的最大公约数（GCD) 恰好为 k，然后从 S 中移除所有选中的整数。

• 每次操作至少必须选择一个整数。
• 整数集合的最大公约数（GCD）是能整除该集合中每个整数的最大正整数 g。例如，(gcd(12, 16) = 4)，(gcd(6, 9, 12) = 3)，且 (gcd(6, 10, 15) = 1)。请注意，​单个整数的 GCD 就是其自身​。

在第一次操作之前，熊猫最多可以选择 S 中的 m 个整数并​修改它们的值​。每个被选中的整数可以被改为 1 到 n 之间的任意值（请注意，这种修改允许 S 包含重复值）。

请你帮助熊猫找出他能成功执行的​最大操作次数​。

格式

输入

• 第一行包含一个整数 T (1 <= T <= 10^4) ，表示测试用例的数量。
• 对于每个测试用例，输入为一行，包含三个整数 n,k,m (1 <= k <= n <= 1e18, 0 <= m <= n)其中：
  • n 是初始多重集的上限；
  • k 是子集所需的 GCD；
  • m 是可修改值的最大数量。

输出

对于每个测试用例，在一行中输出一个整数，表示能成功执行的最大操作次数。

样例

2 
4 1 0 
5 3 1

2
2

限制

• 每个测试用例的时间限制：1 秒
• 每个测试用例的内存限制：1024 兆字节