連続する複数の整数を、以下の手順によっていくつかの集合に分割します。</p>

まず、対象となる整数の区間と、ある整数 P が与えられます。 初期状態では、区間中の整数はそれぞれその整数のみを含む別々の集合に属しています。 そして、区間に属する整数同士のペアのそれぞれについて、その 2 つの整数に共通する P 以上の素因数が存在するならば、その 2 つの整数が属する集合同士を併合して 1 つの集合にする、という操作を行います。

この手順を終えたとき、集合の数はいくつになっているでしょうか？

입력 형식

最初の行はテストケースの数 C を含んでいます。</p>

各テストケースは 1 行で、スペースで区切られた 3 つの整数 A, B, P が含まれます。 A と B はそれぞれ区間の最初と最後の整数で、P は上述した数です。

制約

• 1 ≤ C ≤ 100
• 1 ≤ A ≤ B ≤ 10¹²
• B ≤ A + 1000000
• 2 ≤ P ≤ B

各テストケースにつき、 "Case #X: Y" という文字列を含んだ一行を出力してください。 ここで X は 1 から始まるテストケースの番号であり、Y は集合の個数です。

예제 입력

2
10 20 5
10 20 3

예제 출력

Case #1: 9
Case #2: 7