Need help with this two number theory problems.Give me some hints please. Problem 1:

Given an integer N <= 10^25000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is euler's totient function.

Input: The first line in the input gives the number of test cases T (T<=200), and then T lines follow each containing an integer N.

Output: Output the smallest required value of m.

Sample Input: 1 10

Output: 6

Problem 2:

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of n^k.

Input: Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 2^31) and k (1 ≤ k ≤ 10^7).

Output: For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that n^k contains at least six digits.

Sample Input: 5 123456 1 123456 2 2 31 2 32 29 8751919

Sample Output: Case 1: 123 456 Case 2: 152 936 Case 3: 214 648 Case 4: 429 296 Case 5: 665 669