Check if the door is open or closed

There are ‘N’ doors and ‘N’ people in a house. Each person and door has a unique ID ranging from 1 to ‘N’. A person can change the status of the door i.e, if the door is open then a person can close the door and vice versa. Initially, all the doors are closed and each person wants to change the status of all doors whose ID is a multiple of the ID of the person. You need to find out the final status of all the doors.

The answer should be given in a form of a binary string where ‘0’ represents the closed door and ‘1’ represents the open door. For example, the status “close open close” will form a binary string “010”.

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The only line of each test case contains a single positive integer ‘N’ denoting the number of doors and persons.

Output Format:

The only line of output of each test case should contain a binary string representing the final status of doors.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this in O(N) time and using constant extra space. The output string does not count as extra space.

Constraints:

1 <= T <= 100
1 <= N <= 10^4  

Where ‘T’ is the number of test cases, ‘N’ is the number of doors and persons.

Time Limit: 1 sec

Sample Input 1:

2
2
4

Sample Output 1:

10
1001    

Explanation for sample input 1:

Test case 1:
Initially, all the doors are closed -> 00
The first person has an ID 1 so it will change the status of doors 1(1 * 1) and 2(1 * 2) -> 11
The second person has an ID 2 so it will change the status of door 2 (2 * 1)-> 10

Test case 2:
Initially, all the doors are closed -> 0000
The first person has an ID 1 so it will change the status of door 1, 2, 3 and 4 -> 1111
The second person has an ID 2 so it will change the status of door  2 and 4 -> 1010
The third person has an ID 3 so it will change the status of door 3-> 1000
The fourth person has an ID 4 so it will change the status of door 4 -> 1001

Sample Input 2:

2
6
8

Sample Output 2:

100100
10010000