Description

Hh在历经千辛万苦之后，终于获得了虫箭，为了将替身进化为[镇魂曲]，打败大魔王Xx，Hh必须使用虫箭扎向自己，但是虫箭只认可天选之人，要想进化替身，必须先回答虫箭的问题，如果回答正确，那么Hh就能成功进化替身，否则虫箭会释放毒素，让Hh爆体而亡。

虫箭的问题是这样的：给你所有在 [a,b] 范围内的整数(包含a和b)。一开始每个整数都是独孤的(家族中只有它自己，没有家人)。每次你需要选择两个属于不同家族中的整数，如果这两个整数拥有大于等于p的公共质因数，那么把它们所在的两个家族合并成一个更大的家族。重复上述操作，直到没有可以合并的家族为止。最后一共有多少个整数家族?

很明显，对于不擅长算法的Hh来说，这个问题很难回答，于是Hh使用了他的替身能力[Off Site Help]来求助远在火星的算法大牛Gg，这个问题当然难不到Gg，但是Gg觉得这是一个好机会，可以锻炼Hh的算法能力，于是拒绝了Hh的请求，现在，绝望的Hh只能向你求助，你能帮他解决这个问题吗？

质数：除了1以外，只能够被1和它本身整除的数(1不是质数)。

因数：在数论的叙述中，如果n和d都是整数，而且存在某个整数c，使得n = cd，就说d是n的一个因数，或说n是d的一个倍数。

公因数：如果一个整数同时是几个整数的因数，称这个整数为它们的“公因数”。

公共质因数：是两个数的公因数，同时又是质数的数。

Input Format

首先第一行输入一个正整数t(1≤t≤100)，表示题目有t组测试样例。

接下来的2到t + 1行，每行表示一个输入样例，该行共三个整数 a,b,p(1≤a≤b≤100000, 2≤p≤b)，两数之间用空格隔开。

Output Format

每个测试样例输出一行，其中包含一个正整数，表示最终集合的个数。

1
1 10 2

3

Hint

测试样例说明：对于样例1 10 2，其最终可以划分为3个集合，它们分别是：[1]，[7]，[2,3,4,5,6,8,9,10]

Source

1816 Online Judge 10.100.0.232