``` package test; import java.util.\*; public class Main{ ``` static int m,n; static int[] nn; public static void main(String args[]) { ``` Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.nextLine(); while (n-- > 0) { String string = scanner.nextLine(); nn = new int[string.length()]; check(string); ``` ``` // for (int i = 0; i < nn.length; i++) { // System.out.printf("%d ",nn[i]); // } // System.out.println(); ``` int len = string.length() - nn[nn.length -1 ]; ``` System.out.println(string.length() % len == 0 ? string.substring(0,len) : string); System.out.println(string.length() % len == 0 ? string.length() / len : 1); } ``` } static void check(String s) { ``` for (int i = 1; i < s.length(); i++) { int j = nn[i - 1]; while (j > 0 && s.charAt(i) != s.charAt(j)) { j = nn[ j -1 ]; } if (s.charAt(i) == s.charAt(j)) { j++; } nn[i] = j; } ``` } ``` } ```