OSLO, Norway - Three men accused in Norway of an al Qaeda-linked plot to attack a Danish newspaper that caricatured the Prophet Muhammad pleaded not guilty Tuesday to terror charges as their trial began.

The trial of Mikael Davud, Shawan Sadek Saeed Bujak and David Jakobsen is being seen as a key test of Norway's anti-terror laws. The men had been under surveillance for more than a year when authorities moved to arrest them in July 2010.

Norwegian investigators, who worked with their U.S. counterparts, say the defendants were building a bomb in a basement laboratory -- a plot linked to the same al Qaeda planners behind 2009 schemes to blow up New York's subway and a British shopping mall.

The men deny the terror charges. Prosecutors must prove they worked together in a conspiracy, because a single individual plotting an attack is not covered by Norway's anti-terror laws.

Prosecutor Geir Evanger told the Oslo district court that Davud, the alleged ringleader, received explosives training in Pakistan. They said he conspired with al Qaeda operatives to attack the Danish Jyllands-Posten newspaper, whose 12 cartoons of Muhammad triggered furious protests in Muslim countries in 2006.

Later, the plan was changed to killing Kurt Westergaard, a Danish cartoonist who created one of the most controversial of the 12 drawings, Evanger said.

Islamic law generally opposes any depiction of the prophet, even favorable, for fear it could lead to idolatry.

Bujak and Jakobsen are accused of joining the plot in 2009 and helping to acquire bomb-making chemicals. Police had the men under surveillance and even replaced a key ingredient with a harmless liquid to ensure they wouldn't succeed in building a bomb.

Davud, a 40-year-old ethnic Uighur from China, smiled as the charges were read. He rejects belonging to al Qaeda, denies having traveled to Pakistan and says he has no links to the foiled terror plots in New York and Manchester, England, his lawyer Carl Konow Rieber-Mohn said.

Davud claims he was plotting to attack the Chinese Embassy in Oslo, and the other two defendants were not aware of his plans. Rieber-Mohn said Davud was motivated by "private revenge" related to Beijing's suppression of Uighurs, a Muslim minority in China.

Davud's lawyers said the charges don't come close to meeting the criteria for a terrorist conspiracy under Norwegian law.

Prosecutors made no reference to the Chinese Embassy being the target of the plot in the charges. They plan to present testimony obtained in the U.S. in April from Najibullah Zazi and Zarein Ahmedzay, who have pleaded guilty in the plot to bomb the New York subway, as well as Bryant Neal Vinas, an American al Qaeda recruit.

A U.S. investigator will also testify in the Norwegian trial later this month.

Bujak, an Iraqi Kurd, has confessed that he and Davud planned the attacks against the Danish newspaper and later aimed to target Westergaard. He told the court Tuesday that Davud asked him to get a gun for that purpose.

"Brother believe me, but I am not able to get you a pistol," Bujak recalled telling Davud. He spoke to the court in Kurdish and his comments were translated to Norwegian by an interpreter.

Bujak said he wasn't aware of Davud's alleged links to al Qaeda and described their plans as "just talk." He denied criminal responsibility but said he would accept his punishment if found guilty.

If convicted, the defendants could face up to 12 years in prison.

Jakobsen, an Uzbek national who changed his name after moving to Norway, provided some of the chemicals for the bomb, according to the indictment. His lawyer Rene Ibsen said Jakobsen did not know they were meant for explosives. Ibsen also said Jakobsen had contacted the security police in September 2009 and had later been an informant for the police.

Davud was to address the court on Wednesday.