폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

• 0과 1로만 이루어져 있어야 한다.
• 1이 적어도 하나 있어야 한다.
• 수의 길이가 100 이하이다.
• 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

출력 형식

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

예제 입력

6
17
11011
17
999
125
173

예제 출력

11101
11011
11101
111111111111111111111111111
1000
1011001101