Fujiwara는 커플을 매우 좋아한다.
남학생 명과 여학생 명을 크기의 격자에 배치하려고 한다. 이며, 각 칸에는 정확히 한 명을 배치해야 한다.
변을 공유하는 두 칸에 서로 다른 성별의 학생이 배치되어 있으면 두 학생이 만난다고 하자. 만나는 횟수는 이러한 두 칸의 쌍의 개수이다. 각 쌍은 한 번만 세며, 꼭짓점만 공유하는 두 칸은 세지 않는다.
남학생을 B, 여학생을 G로 나타낼 때, 만나는 횟수가 최대가 되도록 학생들을 배치한 격자를 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 학생들의 배치를 개의 줄에 걸쳐 출력한다. 각 줄은 B와 G로만 이루어진 길이 의 문자열이어야 하며, 각 문자는 해당 칸에 배치한 학생의 성별을 나타낸다.
격자 전체에서 B의 개수는 , G의 개수는 여야 한다. 만나는 횟수는 가능한 최대여야 하며, 가능한 배치가 여러 가지라면 아무거나 하나 출력한다.
테스트 케이스가 입력된 순서대로 격자를 출력한다. 테스트 케이스 사이에 별도의 구분자나 빈 줄을 출력하지 않는다.
여학생만 있으므로 만나는 횟수는 이다.
첫 번째 테스트 케이스에서는 유일한 남학생을 가운데 칸에 배치했다. 상하좌우의 여학생과 만나므로 만나는 횟수는 이다.
두 번째 테스트 케이스에서는 세 남학생이 각각 세 여학생과 만나므로 만나는 횟수는 이다. 두 경우 모두 제시한 배치가 최적이다.
첫 번째 테스트 케이스에서 만나는 횟수는 이고, 두 번째 테스트 케이스에서는 이다. 각각 가능한 최댓값이다.
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 테스트 케이스의 한 줄에 격자의 크기 , 남학생의 수 , 여학생의 수 가 공백으로 구분되어 주어진다.
