Under construction

Still being built. Things may change

RSA Mistake

Interview

Time limit1sMemory limit1024 MB

Summary
Given A and B, output full credit if they are distinct primes, partial credit if A*B has no square factor k^2 with k at least 2, otherwise no credit.
Level

Medium5 of 10

Topics
Math, Number theory
Solved
No attempts yet

Problem

An RSA number is a positive integer nn that is the product of two distinct primes. For example, 10=2⋅510 = 2 \cdot 5 and 77=7⋅1177 = 7 \cdot 11 are RSA numbers, whereas 7=77 = 7, 9=3⋅39 = 3 \cdot 3, and 105=3⋅5⋅7105 = 3 \cdot 5 \cdot 7 are not.

You are teaching a course that covers RSA cryptography. For one assignment, you asked students to generate RSA numbers. They were to submit two positive integers AA and BB. Ideally, these would be distinct prime numbers. Some students submitted incorrect solutions. If they were not distinct primes, partial credit is earned if A⋅BA \cdot B is not an integer multiple of k2k^2 for any integer k≥2k \geq 2. If there is an integer k≥2k \geq 2 such that k2k^2 divides A⋅BA \cdot B, the student receives no credit.

Note: In the sixth sample case, the number 545 528 636 581⋅876 571 629 707545\,528\,636\,581 \cdot 876\,571\,629\,707 is divisible by 1 000 00321\,000\,003^2. In the seventh sample case, the number 431 348 146 441⋅3431\,348\,146\,441 \cdot 3 is divisible by 656 7712656\,771^2.

Input

The input consists of a single line containing two integers AA (2≤A≤10122 \leq A \leq 10^{12}) and BB (2≤B≤10122 \leq B \leq 10^{12}), which are the two submitted numbers.

Output

Display whether the student should receive full credit, partial credit, or no credit for the submitted numbers.

Examples5

  1. Example 1

    Input
    13 23
    
    Expected output
    full credit
    
  2. Example 2

    Input
    35 6
    
    Expected output
    partial credit
    
  3. Example 3

    Input
    4 5
    
    Expected output
    no credit
    
  4. Example 4

    Input
    17 17
    
    Expected output
    no credit
    
  5. Example 5

    Input
    15 21
    
    Expected output
    no credit