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