Big LCM

BLCM(a,b) হলো এমন একটি ফাংশন যে রিটার্ন করে সর্বনিম্ন সংখ্যা যা a হতে b পর্যন্ত সকল পূর্ণসংখ্যা দিয়ে নিঃশেষে বিভাজ্য।

তোমাকে এমন একটি সংখ্যা n বের করতে হবে যেনো BLCM(a,b), cn দ্বারা নিঃশেষে বিভাজ্য হয়।

যদি একাধিক n এর জন্যে এই কথাটি সত্য হয় তবে তোমাকে সবচেয়ে বড় n বের করতে হবে যার জন্যে কথাটি সত্য।

Input

ইনপুট শুরু হবে একটি পূর্ণসংখ্যা T(0 < T ≤ 100) দিয়ে,যা টেস্ট কেস এর সংখ্যা নির্দেশ করে।

পরবর্তী প্রতিটা লাইন এ আরো তিনটি পূর্ণসংখ্যা a, b, c (0 < a ≤ b ≤ 1018 and 1 < c ≤ 1018) থাকবে। যারা উপরে বর্ণিত a, b, c কে নির্দেশ করে।

Subtask Details :

Subtask 1, 10% পয়েন্ট এর জন্যে: (0 < a≤ b ≤ 10 and 1 < c ≤ 10)

Subtask 2, 20% পয়েন্ট এর জন্যে: (0 < a≤ b ≤ 32 and 1 < c ≤ 105)

Subtask 3,40% পয়েন্ট এর জন্যে: (0 < a ≤ b ≤ 105 and 1 < c ≤ 109)

Subtask 4, 60% পয়েন্ট এর জন্যে: (0 < a ≤ b ≤ 109 and 1 < c ≤ 109)

Subtask 5, 100% পয়েন্ট এর জন্যে, (0 < a ≤ b ≤ 1018 and 1 < c ≤ 1018)

Output

প্রতিটি টেস্ট কেস এর জন্যে একটি পূর্ণসংখ্যা প্রিন্ট কর, যা ওই টেস্ট কেস এর উত্তর প্রকাশ করে।

Sample

Input	Output
2 1 5 2 5 7 4	2 0