Skip to content

Latest commit

 

History

History
35 lines (21 loc) · 1.72 KB

ProblemStatement.md

File metadata and controls

35 lines (21 loc) · 1.72 KB

Primal Number

time limit per test:1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

One day, Prerak was usually wandering here and there and was lost in his thoughts. He had just read about how to check whether a number is a perfect square or not from the internet. However, he found it boring so he decided to create his own number "Primal Number."

Primal Number is a special type of number that follows two conditions:

  • The number is a perfect square.
  • The number of factors of a number is also a perfect square.

A perfect square is a number that can be expressed as the product of an integer by itself . For example, 25 is a perfect square because it is the product of integer 5 by itself, 5 × 5 = 25. However, 21 is not a perfect square number because it cannot be expressed as the product of two same integers.

Prerak had a question in his mind. How many Primal numbers are there from 1 to n(inclusive)?

He thought it hard but couldn't solve the problem. Ultimately, he asked you to solve this problem for him. In addition to this, he also asked him to print those numbers for him.

Input:

The first line contains a single integer t (1≤t≤100), denoting the number of test cases.

The first line in each test case contains a single integer n(1≤n≤107).

The sum of n over all test cases doesn't exceed 107.

Output:

For each test case:

The first line contains the number of primal numbers from 1 to n(inclusive).

The second line contains the primal numbers, separated by a space.